割り当てのカスタム割り当てがあり、ほぼ完了しています。残念ながら、診断できないように見える問題に遭遇しました。割り当ては、キャッシュ割り当て (< 2kB) と領域割り当て (> 2kB) を行う 2 つの関数によって処理されます。ここに私のメモリ構造があります:
23 typedef struct slab {
24 void *addr;
25 int bm[SLAB_SIZE/8/(8*sizeof(int))]; // bitmap for the slab
26 struct slab *next;
27 } slab;
40 typedef struct {
41 int alloc_unit;
42 slab S;
43 } cache;
46 typedef struct { // structure for the entire memory
47 cache C[9];
48 region *R;
49 } memory;
(注:ビットマップはすべてのスラブで同じサイズで、少し非効率的ですが、どこにでも大量の重複コードがあるのではなく、最初にこのように機能させたかったのです)
問題は、 8 バイトを超えるすべての割り当てに対して機能するかなり複雑な allocate_cache 関数にあります。16B、32B、... 2kB のインスタンスを 50 ~ 100k 割り当てて、ある程度集中的にテストしましたが、すべて正常に動作しました。ロジックは次のとおりです。それぞれの先頭cache
にシングルが含まれていslab
ます。それぞれslab
が持つことができますがSLAB_SIZE/alloc_unit slots
、スラブごとに異なります (したがって、2kB スラブには 2kB メモリの最大 32 スロットを含めることができ、1kB スラブには 64 スロットを含めることができます)。
私の割り当てキャッシュ関数は次のとおりです。
55 void *allocate_cache(unsigned int size) { // cache allocation
56
57 // 1. Select the cache
58 int ci = 0, si, pos, bmi; // cache_index, slot_index, position, bitmap index
59 int slbn = 0; // slab number
60 unsigned short check = 0;
61 while ((size-1) >> (ci+3))
62 ci++;
63 // 2. Find a slot
64 bmi = 0; // bitmap index
65 int lbmi = 0; // 'linked' bitmap index
66 int counter = 0;
67 int coefficient = SLAB_SIZE/M.C[ci].alloc_unit;
68 do {
69 pos = find_zero_bit(M.C[ci].S.bm[bmi]); // Find the first zero bit in the bitmap
70 if (pos == -1) { bmi++; // If bm[bmi] does not have free slots, keep checking the map...
71 if(bmi == coefficient/(8*sizeof(int))){ // If bmi is max size, then we need to check
72 slab *next_slab = &M.C[ci].S; // the following slabs, if there are any.
73 while(next_slab->next != NULL){ // While there are additional slabs
74 next_slab = next_slab->next;
75 slbn++; // Increment the slab counter.
76 while(lbmi < bmi) { // Go through the slots in this slab too
77 pos = find_zero_bit(next_slab->bm[lbmi]); // Until a free slot has been found
78 if(pos != -1) { // If a free slot has been found...
79 set_bit(&(next_slab->bm[lbmi]), pos); // Mark it as occupied...
80 check = 1;
81 break; // And break out of the loop.
82 }
83 lbmi++; counter++;
84 }
85 if(check == 1) break; // If we already found a free slot in one of the slots, break.
86 lbmi = 0;
87 }
88 }
89 }
90 else break;
91 } while(bmi < coefficient/(8*sizeof(int)));
92 si = bmi*32 + counter*32 + (pos - 1);
93 // compute the slot index based on bmi, pos and counter
94 // 3.a Slot not found => allocate a new slab
95 printf("pos = %d , si = %d, bmi = %d, slbn = %d lbmi = %d counter = %d\n", pos, si, bmi, slbn, lbmi, counter); // sanity check
96 if(pos == 32 && ((si+1) % coefficient == 0)) {
97 printf("===== SLAB FULL. NOW CREATING NEW SLAB. =====\n");
98 // Initialize a new slab.
99 slab *temp = &M.C[ci].S; // Set temp to the initially allocated slab
100 while(temp->next != NULL) temp = temp->next; // Get the last currently allocated slab
101 void *new_addr = mmap(NULL, SLAB_SIZE + sizeof(slab), PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
102 slab *new_slab = new_addr;
103 new_slab->addr = (char *)new_addr + sizeof(slab);
104 temp->next = new_slab; // Set the new slab as the one following the existing slabs
105 temp->next->addr = new_slab->addr; // Set the new slab's address to the newly mmap'd address
106 temp->next->next = NULL; // Set the new slab's NEXT pointer to NULL
107 bzero(&new_slab->bm, SLAB_SIZE/M.C[ci].alloc_unit/8); // Zero-out the new slab's bitmap
108 if(temp->addr == MAP_FAILED) { // Check if mmap succeeded...
109 printf("mmap failed. Exiting...\n");
110 exit(-1);
111 }
112 printf("Allocated memory for cache %d's slab %d at address %p\n", ci, slbn, temp->next);
113 }
114 printf("Use cache %d , slab %d (allocation unit size: %d)\n", ci, slbn,M.C[ci].alloc_unit);
115 printf("Found slot %d in slab %d of cache %d\n", si % (SLAB_SIZE/M.C[ci].alloc_unit), slbn, ci);
116
117 // 3.b Slot found
118
119 if(M.C[ci].S.addr == NULL) { // Slab not allocated yet
120 M.C[ci].S.addr = mmap(NULL, SLAB_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
121 printf("Allocated memory for cache %d's slab at address %p\n", ci, M.C[ci].S.addr);
122 }
123
124 if(M.C[ci].S.addr == MAP_FAILED) {
125 perror("mmap failed\n");
126 exit(-1);
127 }
128 set_bit(&M.C[ci].S.bm[bmi], pos); // mark the bit as occupied
129
130 // 4. Return address
131
132 return M.C[ci].S.addr + si*M.C[ci].alloc_unit;
133 }
問題のある行はのようline 77
です。GDB を実行すると、次の結果が得られます。
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400847 in allocate_cache (size=5) at allocator.c:77
77 pos = find_zero_bit(next_slab->bm[lbmi]); // Until a free slot has been found
ただし、これがどのように当てはまるかはわかりません。next_slab
は正しく初期化されています ( line 101-111
、および bm は bzero ( を使用してゼロに設定されたビットマップline 107
です)。したがって、これは別の問題であり、107 行目に表示されるだけであると信じる傾向がありますが、診断できていません。数日間。
また、スラブ構造体アドレスを上書きするような愚かなことをしていないことを確認するためにロジックを調べてきましたが、私の知る限り、mmap が提供する範囲ではこれが発生しません。
どんな助けや指針も大歓迎です。
PS。なんらかの方法でコードを再フォーマットしてほしい場合はお知らせください。少し見苦しいかもしれません。
編集:開始時のキャッシュの初期化は私のinit_memory()
関数で行われます。キャッシュに関連する行は次のとおりです。
161 // Init the caches
162 for(i =0; i<9; i++) {
163 M.C[i].alloc_unit = 8<<i;
164 M.C[i].S.addr = NULL;
165 M.C[i].S.next = NULL;
166 bzero(M.C[i].S.bm, SLAB_SIZE/M.C[i].alloc_unit/8);
167 }
更新: エラーが見つかったようです。何よりも論理エラーでした。私のビットマップ配列のサイズは 256、つまり 0..255 でした。8 バイトの割り当ての場合、ビットマップは正しく 256 に設定され、最後の空きスロットが使い果たされたことを示しますが、これは私のビットマップの定義と競合し、bm[256] は不正な読み取りです。したがって、未定義の動作です。ビットマップ配列のサイズを 1 増やすだけで問題を修正しましたint bm[((SLAB_SIZE/8)/(8*sizeof(int)))+1];
。
これを理解しようとするのを手伝ってくれたKoushikに感謝します。彼がいくつかの場所に括弧を追加することを提案したことで、今後のデバッグの頭痛の種もいくつか解消されたでしょう。