1

割り当てのカスタム割り当てがあり、ほぼ完了しています。残念ながら、診断できないように見える問題に遭遇しました。割り当ては、キャッシュ割り当て (< 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に感謝します。彼がいくつかの場所に括弧を追加することを提案したことで、今後のデバッグの頭痛の種もいくつか解消されたでしょう。

4

1 に答える 1