Về việc tổ chức bảng MACVLAN với 10000 phần tử

Bài viết này là phần ứng dụng của bài viết trước về bảng băm (hash table). Nếu các bạn chưa nắm được khái niệm về tổ chức dữ liệu trong bảng băm. Các bạn vui lòng đọc lại bài viết trước tại đây

Các kiến thức cơ sở

Bảng MACVLAN là một cơ sở dữ liệu được sử dụng trong các thiết bị mạng như Router/Switch/ONT/OLT với mục đích tìm kiếm cổng ra của một bản tin dựa vào địa chỉ MAC đích của bản tin đó. Nếu các bạn chưa biết địa chỉ MAC của một cổng mạng là gì, các bạn có thể vào command line của hệ điều hành Linux và gõ ifconfig

Địa chỉ MAC (màu vàng) hay còn gọi là địa chỉ vật lý (có độ dài 48bit) là địa chỉ duy nhất được gắn cho mỗi cổng mạng của một máy tính, địa chỉ này được sử dụng để nhận biết chính xác từng máy trong môi trường mạng IP. Xem xét một sơ đồ mạng như sau

Giả sử máy tính A có địa chỉ MACA, máy tính B có địa chỉ MACB, máy tính C có địa chỉ MACC được cắm lần lượt vào cổng 1, 2, 3 của Switch. Trong quá trình hoạt động của mình, Switch sẽ tìm cách học các địa chỉ này và duy trì một bảng MAC tương ứng

Vlan	Mac address	Type	Port
1	MACA	Dynamic	1
1	MACB	Dynamic	2
1	MACC	Dynamic	3

Như vậy Switch sẽ biết máy tính A,B,C nằm lần lượt trên cổng 1,2,3 và khi có một bản tin hướng đến các máy tính này thì Switch sẽ chuyển tiếp ra các cổng tương ứng. Chúng ta có thể nhìn thấy bảng này trên các Router/Switch của Cisco bằng command-line show mac address-table

Bởi việc xử lý tìm kiếm được thực hiện trên từng bản tin, nên việc tổ chức cơ sở dữ liệu trên Switch đòi hỏi thời gian tìm kiếm phải nhanh nhất có thể. Đồng thời trong các mạng LAN lớn, số lượng máy tính có thể lên tới hàng vạn, nên số lượng địa chỉ MAC sẽ tăng lên tương ứng, việc tổ chức cơ sở dữ liệu đòi hỏi sự cân bằng giữa bộ nhớ được cấp phát tới bảng và thời gian tìm kiếm

Tổ chức cơ sở dữ liệu của bảng MAC với 10000 bản ghi

Ở bài viết trước, tôi đã trình bày một phương thức tổ chức cơ sở dữ liệu dạng bảng băm, trong bài viết này chúng ta sẽ sử dụng phương thức tổ chức cơ sở dữ liệu trên để tổ chức bảng MACVLAN với 10000 bản ghi

Các giao diện chính của bảng

Bảng có các giao diện được đưa tới người sử dụng như sau

Khởi tạo bảng, cấp phát bộ nhớ cho bảng
Chèn một bản ghi dựa vào địa chỉ MAC
Xóa một bản ghi dựa vào địa chỉ MAC
Tìm kiếm một bản ghi dựa vào địa chỉ MAC
In ra tất cả các bản ghi trong bảng
Xóa bảng, giải phóng bộ nhớ bảng và các cấu trúc dữ liệu quản lý bản ghi

Khởi tạo bảng và cấp phát bộ nhớ cho hoạt động của bảng

Khởi tạo bảng là phương thức được gọi đầu tiên trước tất cả các phương thức khác. Khởi tạo bảng sẽ cấp phát bộ nhớ cho bảng và toàn bộ hoạt động quản lý bản ghi của bảng. Hàm khởi tạo bảng sẽ gọi tới phương thức Table_new của bảng băm. Hàm này đòi hỏi phải truyền vào số lượng tối đa các bản ghi sẽ tổ chức trong bảng, một hàm băm (hash) để tìm kiếm vị trí của danh sách liên kết mà bản ghi được lưu giữ và hàm so sánh (compare) để tìm kiếm vị trí của bản ghi trong danh sách liên kết

Trước hết chúng ta tìm hiểu về thiết kế một hàm băm (hash) cho bảng MACVLAN. Có rất nhiều nghiên cứu và các khuyến nghị khác nhau về phương pháp thiết kế hàm băm. Các yêu cầu cơ bản của hàm băm như sau

Hàm lấy vào một tập các dữ liệu lớn và đưa ra tập các dữ liệu nhỏ hơn (1)
Hàm phải có khả năng phân phối đều trên tập dữ liệu đầu ra (2)
Hàm phải hoạt động nhanh, do đó hàm càng đơn giản càng tốt (3)

Tôi xin giải thích một chút về các yêu cầu trên, với yêu cầu số (1), ví dụ như trong trường hợp của chúng ta tổ chức bảng MACVLAN sẽ lấy vào địa chỉ MAC (có độ dài 48bit) và trả ra một chỉ số (có độ dài 8 bit), chỉ số này sẽ sử dụng làm chỉ số cho mảng địa chỉ các danh sách liên kết chứa các bản ghi. Như thế mảng các địa chỉ này có độ dài 2^8-1 = 255 phần tử. Nếu hàm băm trả ra tập dữ liệu có độ dài lớn hơn 48-bit, như thế sẽ cần cấp phát một mảng có độ dài lớn hơn 2^48 thì sẽ quá lớn vượt quá khả năng bộ nhớ của đa số máy tính.

Với yêu cầu số (2), địa chỉ MAC là một số có giá trị từ 00:00:00:00:00:00 tới FF:FF:FF:FF:FF:FF. Ngoại trừ một số địa chỉ được cấp phát đặc biệt (địa chỉ multicast, địa chỉ broadcast, các địa chỉ cấp phát dành riêng bởi IANA, …) thì địa chỉ MAC hoàn toàn là một số ngẫu nhiên trong khoảng giá trị trên. Khi địa chỉ MAC chạy trong khoảng tối thiểu-tối đa thì hàm băm phải trả ra kết quả là một phân phối đều trong khoảng 0-255 (vì kết quả ra là 8bit). Vì kết quả đầu ra này sẽ dùng làm chỉ số hóa cho mảng các địa chỉ danh sách liên kết của bản ghi nên nếu kết quả không phải là một phân phối đều thì sẽ khiến cho số lượng bản ghi tại một vị trí sẽ nhiều hơn vượt trội so với các vị trí khác. Điều này sẽ khiến cho thời gian tìm kiếm một bản ghi khi biết địa chỉ của danh sách liên kết chứa bản ghi trong trường hợp tồi nhất sẽ tăng lên. Chúng ta có 10000 bản ghi và có 255 vị trí chứa danh sách liên kết, chúng ta sẽ muốn rằng mỗi vị trí sẽ có 10000/255 ~ 40 bản ghi chứ không phải nơi thì có hàng trăm bản ghi, nơi thì lại chẳng có bản ghi nào, phải không ạ. Hình dưới đây mô tả một hàm hash tạo ra phân phối đều, khi tập đầu vào đi hết khoảng giá trị của nó, số lượng mỗi phần tử ở tập đầu ra là bằng nhau

Cuối cùng với yêu cầu số (3), rõ ràng là hàm hoạt động càng nhanh càng tốt bởi hàm được gọi ở hầu hết các phương thức quan trọng của bảng. Nên hàm hoạt động càng nhanh thì các hoạt động tìm kiếm/xóa/sửa/thêm bản ghi sẽ hoạt động càng nhanh, sẽ càng tối ưu thời gian xử lý

Với các yêu cầu trên, chúng ta xem xét thêm cấu trúc địa chỉ của địa chỉ MAC :

Chúng ta thấy rằng trong 48bit địa chỉ MAC, có 24 bit đầu là địa chỉ của nhà sản xuất, 24bit sau sẽ gắn cho cạc mạng. Như thế thay vì đưa cả 48bit địa chỉ MAC vào hàm băm, nếu chúng ta chỉ đưa 24bit đầu thì chúng ta sẽ nhóm được tất cả địa chỉ MAC của một hãng vào một danh sách liên kết duy nhất, điều này sẽ tạo thuận lợi cho việc quản lý cũng như thống kê.

Hàm băm của bảng MACVLAN sẽ được thiết kế như sau:

#define GOLDEN_RATIO_PRIME_24 0x9e3701UL

unsigned int hash_24(unsigned int val, unsigned int bits)

{

unsigned int hash = val * GOLDEN_RATIO_PRIME_24;

return (hash >> (24 - bits)) & ((1 << bits) - 1);

}

unsigned mac_hash(const void *key)

{

unsigned char *macaddr = (unsigned char *)key;

unsigned int mackey = 0;

unsigned machash;

mackey = (macaddr[0] << 16) | (macaddr[1] << 8) | (macaddr[2]);

machash = (unsigned )hash_24(mackey, L1_HASHKEY_BIT);

LOG("hashpos %u\n", machash);

return machash;

}

Trong hàm mac_hash, chúng ta thấy rằng 24 bit đầu của địa chỉ mac sẽ được dùng để tạo ra mackey, mackey này sẽ làm đầu vào của hàm hash_24, đầu ra của hàm hash_24 sẽ trả ra một giá trị 8bit (chạy từ 0-255).

Trong hàm hash_24 ta thấy đầu ra sẽ được tính toán bằng cách nhân với một giá trị định nghĩa trước GOLDEN_RATIO_PRIME_24. Làm thế nào để tính toán được giá trị này? Chúng ta sẽ tìm hiểu một chút. Nếu bạn chưa từng nghe tới TỶ LỆ VÀNG trong toán học. Xin mời đọc qua một chút tại đây
Tỷ lệ vàng là giá trị 1.618. Ưu điểm của tỷ lệ vàng là nó sẽ tạo ra một phân phối đều các đầu ra trên một tập đầu vào ngẫu nhiên như trong yêu cầu số (2) của hàm băm. Đầu vào của hàm là một giá trị 24-bit, cho nên tỷ lệ vàng của 24-bit này là (2^24-1)/1.618 ~ 0x9e3701 (Lấy tròn về 2^23+2^21−2^17+2^14−2^11−2^8 +1 để tối ưu cho phép nhân). Chúng ta chỉ lấy 8-bit cao nhất trong kết quả của phép nhân với tỷ lệ vàng (bạn có thể lấy 8-bit thấp nhất, sẽ không ai cản bạn đâu ạ) bằng phép AND bit với 0xFF. Bởi vì tỷ lệ vàng cũng là tỷ lệ hội tụ của hai số liên tiếp trong dãy Fibonacci, cho nên phương pháp xây dựng hàm hash theo tỷ lệ vàng còn được gọi là Fibonacci hash.

Như vậy chúng ta đã đi qua phần khó nhất của việc tổ chức bảng MACVLAN, chúng ta đi tiếp tới hàm so sánh để tìm bản ghi khi biết địa chỉ của danh sách liên kết chứa bản ghi

int mac_cmp(const void *x, const void *y)
{

return memcmp(x, y, MACADDR_LEN);

}

Hàm đưa vào toàn bộ địa chỉ MAC, so sánh để tìm kiếm bản ghi phù hợp và trả ra kết quả. Nếu tìm thấy, hàm trả lại 0, ngược lại hàm sẽ trả ra giá trị khác 0

Khi các đầu vào đã đầy đủ, hàm khởi tạo bảng và cấp phát bộ nhớ cho bảng

Table_T mactable;

int macv_init(void)

{

mactable = Table_new(10000, mac_cmp, mac_hash);

if(NULL == mactable)

{

LOG("table new error\n");

return ERR_TABLE_NEW;

}

return SUCCESS;

}

Chèn/Xóa/Tìm một bản ghi dựa vào key.

Bởi vì hàm sử dụng framework bảng băm, cho nên các giao diện này được xây dựng thật dễ dàng

mac_vlan_t *macv_insert(mac_vlan_t *mace)

{

return Table_put(mactable, mace->macaddr, mace);

}

mac_vlan_t *macv_remove_by_macaddr(unsigned char *macaddr)

{

return Table_remove(mactable, (const void *)macaddr);

}

mac_vlan_t *macv_find_by_macaddr(unsigned char *macaddr)

{

return Table_get(mactable, (const void *)macaddr);

}

Lưu ý rằng đối với giao diện chèn một phần tử dựa vào key, hàm sẽ lấy vào một cấu trúc dữ liệu do người dùng chỉ định. Cấu trúc dữ liệu này chính là bản ghi cần được lưu giữ trong bảng băm

typedef struct mac_vlan_s

{

unsigned int vlanid;

unsigned char macaddr[MACADDR_LEN];

unsigned int inc_port;

unsigned int status;

} mac_vlan_t;

Nội dung bản ghi chứa các thông tin của bảng MACVLAN, bao gồm VLAN ID, địa chỉ MAC, giá trị này cũng chính là Primary Key của bảng, số hiệu cổng mạng của Switch mà từ đó địa chỉ MAC được học và phương pháp học, phương pháp này có hai giá trị DYNAMIC nghĩa là học động thông qua trao đổi các bản tin giữa máy tính và Switch hoặc STATIC - học tĩnh thông qua cấu hình từ Administrator. Bản ghi này cần được cấp phát bộ nhớ từ người sử dụng và truyền tới hàm INSERT, do đó người sử dụng phải tự giải phóng bộ nhớ của bản ghi khi bản ghi không còn được sử dụng, hàm REMOVE bản ghi dựa vào key chỉ xóa các cấu trúc dữ liệu quản lý bản ghi chứ không xóa bản ghi.

In ra tất cả các bản ghi trong bảng

Hàm in ra tất cả các bản ghi của bảng MACVLAN sử dụng phương thức Table_toArray của bảng để lưu lại tất cả địa chỉ của các bản ghi vào một mảng, địa chỉ MAC cũng sẽ được lưu tương ứng với từng bản ghi. Sử dụng phương thức này giúp chúng ta dễ dàng truy vấn thông tin của toàn bộ các bản ghi

int macv_total_record(void)

{

return Table_length(mactable);

}

void show_macv(void)

{

int i;

void **array = Table_toArray(mactable, NULL);

unsigned char *macaddr;

mac_vlan_t *macvlan;

LOG("--------------------------------------------\n\n");

LOG("Vlan Mac Address Type Port\n");

LOG("---- --------------- ------- -----\n");

for(i=0; array[i]; i+=2)

{

macaddr = (unsigned char *)(array[i]);

macvlan = (mac_vlan_t *)(array[i+1]);

LOG("%4d %02x:%02x:%02x:%02x:%02x:%02x %7s %4d\n", macvlan->vlanid, macvlan->macaddr[0], macvlan->macaddr[1], macvlan->macaddr[2], macvlan->macaddr[3], macvlan->macaddr[4], macvlan->macaddr[5], macvlan->status==1?"DYNAMIC":"STATIC", macvlan->inc_port);

}

LOG("Total of record %5d\n", macv_total_record());

free(array);

}

Và một phần mềm tốt thì đồng nghĩa với việc có một giao diện đẹp, vì thế hàm in tất cả các bản ghi sẽ định dạng in như là vendor Cisco đã định dạng

Xóa bảng, giải phóng bộ nhớ bảng và các cấu trúc dữ liệu quản lý bản ghi

Việc xóa bảng cũng sử dụng phương thức xóa bảng của bảng băm. Tuy nhiên chúng ta nhớ rằng khi INSERT các bản ghi vào bảng, người dùng phải cấp phát bộ nhớ cho các bản ghi, cho nên tại đây người dùng phải tự giải phóng hết các bản ghi đã cấp phát. Việc xóa bảng sẽ không giải phóng các bản ghi mà chỉ giải phóng các cấu trúc quản lý bản ghi và chính bản thân bảng MACVLAN

void freeall_record(const void *key, void **value, void *cl)

{

if(*value)

{

free(*value);

}

void macv_delete_table(void)

{

Table_map(mactable, freeall_record, NULL);

Table_free(&mactable);

}

Chúng ta sử dụng phương thức Table_map của bảng băm và truyền vào đó hàm freeall_record để giải phóng tất cả các bản ghi trước khi xóa bảng. Chúng ta nhớ rằng phương thức Table_map sẽ duyệt qua tất cả các bản ghi của bảng, và chỉ cần truyền vào đó hàm giải phóng bộ nhớ là tất cả các bản ghi sẽ được tự động giải phóng.

Như vậy chúng ta đã kết thúc tất cả các giao diện quan trọng của bảng MACVLAN. Phần còn lại chỉ là các hàm được tôi viết để test các giao diện này. Các bạn có thể xóa nó trước khi release.

#define INSERT_TEST 10000

#define MACSTR_LEN 150

#define LEARNTYPE_LEN 30

mac_vlan_t *create_random_mac_vlan(void)

{

int i;

mac_vlan_t *mac_vlan_e = malloc(sizeof(mac_vlan_t));

if(NULL == mac_vlan_e)

{

return NULL;

}

mac_vlan_e->vlanid = (unsigned int )(random()%2000);

mac_vlan_e->inc_port = (unsigned int )(random()%24);

mac_vlan_e->status = (unsigned int )(random()%2);

for(i=0;i<MACADDR_LEN;i++)

mac_vlan_e->macaddr[i] = (unsigned char)(((unsigned int)random()) & 0x000000ff);

DEBUG("create %02x:%02x:%02x:%02x:%02x:%02x vlanid %d key %p macvlan %p \n",mac_vlan_e->macaddr[0], mac_vlan_e->macaddr[1],mac_vlan_e->macaddr[2],

mac_vlan_e->macaddr[3], mac_vlan_e->macaddr[4], mac_vlan_e->macaddr[5], mac_vlan_e->vlanid, &(mac_vlan_e->macaddr[0]), mac_vlan_e);

return mac_vlan_e;

}

int macv_insert_test(unsigned int num_insert_test)

{

int i;

for(i=0;i<num_insert_test;i++)

{

mac_vlan_t *mace = create_random_mac_vlan();

macv_insert(mace);

}

return i;

}

int main(void)

{

mac_vlan_t *found_mace = NULL, *add_mace = NULL;

char macstr[MACSTR_LEN] = {0};

unsigned char macaddr[MACADDR_LEN] = {0};

int vlanid;

char learntype[LEARNTYPE_LEN] = {0};

int port;

char command;

int numread;

macv_init(INSERT_TEST);

macv_insert_test(INSERT_TEST/2000);

LOG("Test bin already add %d record to mac table.Let type your command to query\n ", INSERT_TEST/2000);

while(1)

{

memset(macstr, 0x00, MACSTR_LEN);

memset(learntype, 0x00, LEARNTYPE_LEN);

port = vlanid = 0;

fgets(macstr, MACSTR_LEN, stdin);

// printf("Got str %s\n", macstr);

numread = sscanf(macstr, "%c %*s %02x:%02x:%02x:%02x:%02x:%02x %*s %d %*s %s %*s %d",&command ,&macaddr[0], &macaddr[1], &macaddr[2], &macaddr[3], &macaddr[4], &macaddr[5], &vlanid, learntype, &port);

if(command == 'r')

{

found_mace = macv_remove_by_macaddr(macaddr);

if(NULL == found_mace)

{

LOG("Address %02x:%02x:%02x:%02x:%02x:%02x not found in table, current total record %d\n",macaddr[0], macaddr[1], macaddr[2], macaddr[3], macaddr[4], macaddr[5] ,Table_length(mactable));

}

else

{

LOG("Address %02x:%02x:%02x:%02x:%02x:%02x deleted from table, current total record %d\n", macaddr[0], macaddr[1], macaddr[2], macaddr[3], macaddr[4], macaddr[5],Table_length(mactable));

free(found_mace);

}

continue;

}

else if(command == 'a')

{

if(0 >= vlanid || 0 >= port || 2048 < vlanid || 10000 < port)

{

LOG("Don't have info to add mace\n");

continue;

}

add_mace = malloc(sizeof(mac_vlan_t));

add_mace->vlanid = vlanid;

add_mace->inc_port = port;

memcpy(add_mace->macaddr, macaddr, MACADDR_LEN);

if(0 == strcmp(learntype, "STATIC"))

add_mace->status = 0;

else

add_mace->status = 1;

found_mace = macv_insert(add_mace);

if(NULL != found_mace)

{

LOG("Record of mac %02x:%02x:%02x:%02x:%02x:%02x existing in table. Info updated and current total record %d\n", macaddr[0], macaddr[1], macaddr[2], macaddr[3], macaddr[4], macaddr[5], Table_length(mactable));

}

else

{

LOG("New record of mac %02x:%02x:%02x:%02x:%02x:%02x added to table, current total record %d\n", macaddr[0], macaddr[1], macaddr[2], macaddr[3], macaddr[4], macaddr[5], Table_length(mactable));

}

continue;

}

else if(command == 's')

{

show_macv();

continue;

}

else if(command == 'e')

{

macv_delete_table();

LOG("Good bye !!!");

break;

}

else

{

LOG("Unknown command %c.Type a-add, r-remove, s-show, e-exit. example \n", command);

LOG("a mac c9:9a:66:32:0d:b7 vlanid 100 learntype DYNAMIC port 102\n");

LOG("r mac c9:9a:66:32:0d:b7\n");

LOG("s\n");

LOG("e\n");

continue;

}

return 0;

}

Phần test sẽ tạo ra 5 bản ghi được INSERT tự động vào bảng (các bạn có thể dễ dàng sửa code để tạo ra 10000 bản ghi, tôi chỉ tạo 5 vì muốn test hàm show), bảng sẽ được thao tác thông qua lệnh từ command-line

Lệnh	Mô tả	Ví dụ
s	Hiển thị nội dung tất cả các bản ghi trong bảng	S
r	Xóa một bản ghi dựa vào địa chỉ MAC	r mac c9:9a:66:32:0d:b7
a	Thêm một bản ghi dựa vào địa chỉ MAC, nếu bản ghi đã tồn tại, update thông tin bản ghi	a mac c9:9a:66:32:0d:b7 vlanid 100 learntype DYNAMIC port 102
e	Thoát khỏi chương trình, xóa tất cả các bản ghi, xóa bảng	E

Enjoy your result

Đánh giá hiệu năng phương pháp

Hiệu năng của phương pháp này phụ thuộc rất lớn vào giải thuật của hàm băm. Có rất nhiều nghiên cứu đã đưa ra các hàm băm rất phức tạp. Hàm băm tôi sử dụng trong bài viết này cũng được sử dụng trong mã nguồn của Linux kernel. Tuy nhiên hàm băm này thực sự chỉ tối ưu cho số lượng bản ghi là 2^24 = 16777216. Có lẽ chúng ta cần tìm một hàm băm khác tối ưu chỉ cho 10000 bản ghi. Phần này xin phép được dành cho độc giả.

Với 10000 bản ghi và 255 vị trí lưu các danh sách liên kết, trong trường hợp cả 10000 bản ghi được điền đầy, mỗi danh sách liên kết sẽ có khoảng 40 bản ghi, như vậy trường hợp xấu nhất, hàm compare sẽ được gọi 40 lần để tìm được một bản ghi, như thế vẫn khá tồi, nhưng chúng ta có thể dễ dàng tăng số lượng bit đầu ra, như thế số lượng bản ghi trong một danh sách liên kết sẽ giảm xuống.

Như vậy chúng ta đã tạo ra một bảng MACVLAN 10000 bản ghi dựa vào bảng băm. Trong bài viết kế tiếp tôi sẽ trình bày phương pháp sử dụng hash table để tổ chức cơ sở dữ liệu với 1 triệu bản ghi.

Toàn bộ mã nguồn của framework các bạn có thê download tại GitHub của Nhã Uyên Education
https://github.com/nhauyeneducation/linux_systemtraining

Tin học Nhã Uyên là một tổ chức thành lập với mục tiêu đào tạo kỹ sư lập trình hệ thống, kỹ sư lập trình nhúng và kỹ sư lập trình mạng trên nền tảng hệ điều hành Linux/Unix tại Việt Nam.
Mời các bạn vào Facebook của Tin học Nhã Uyên tại

https://www.facebook.com/tinhocnhauyen/ để theo dõi các bài viết kỹ thuật chất lượng tiếp theo của Tin học Nhã Uyên. Xin trân trọng cảm ơn các bạn

NhaUyen_Education

Search This Blog