malloc.c ではビンにアクセスしたり、リストを連結解除(アンリンク、unlink)するマクロが用意されています。
malloc.c(https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c).
1389 typedef struct malloc_chunk *mbinptr; 1390 1391 /* addressing -- note that bin_at(0) does not exist */ 1392 #define bin_at(m, i) \ 1393 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \ 1394 - offsetof (struct malloc_chunk, fd)) 1395 1396 /* analog of ++bin */ 1397 #define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1))) 1398 1399 /* Reminders about list directionality within bins */ 1400 #define first(b) ((b)->fd) 1401 #define last(b) ((b)->bk) 1402 1403 /* Take a chunk off a bin list */ 1404 #define unlink(AV, P, BK, FD) { \ 1405 if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0)) \ 1406 malloc_printerr ("corrupted size vs. prev_size"); \ 1407 FD = P->fd; \ 1408 BK = P->bk; \ 1409 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \ 1410 malloc_printerr ("corrupted double-linked list"); \ 1411 else { \ 1412 FD->bk = BK; \ 1413 BK->fd = FD; \ 1414 if (!in_smallbin_range (chunksize_nomask (P)) \ 1415 && __builtin_expect (P->fd_nextsize != NULL, 0)) { \ 1416 if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \ 1417 || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \ 1418 malloc_printerr ("corrupted double-linked list (not small)"); \ 1419 if (FD->fd_nextsize == NULL) { \ 1420 if (P->fd_nextsize == P) \ 1421 FD->fd_nextsize = FD->bk_nextsize = FD; \ 1422 else { \ 1423 FD->fd_nextsize = P->fd_nextsize; \ 1424 FD->bk_nextsize = P->bk_nextsize; \ 1425 P->fd_nextsize->bk_nextsize = FD; \ 1426 P->bk_nextsize->fd_nextsize = FD; \ 1427 } \ 1428 } else { \ 1429 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \ 1430 P->bk_nextsize->fd_nextsize = P->fd_nextsize; \ 1431 } \ 1432 } \ 1433 } \ 1434 }
前にも説明しましたが bin_at() マクロは指定したインデックスのチャンクにアクセスできるようになっています。
malloc.c(https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c).
1392 #define bin_at(m, i) \ 1393 (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \ 1394 - offsetof (struct malloc_chunk, fd))
このマクロは bins[] 配列が fd と bk の 2 つからなるために 2 の倍数に変換していますね。
後は malloc_chunk 構造体のメンバー fd のオフセットを引いて調整しています。
next_bin / first / last は malloc_chunk 構造体のメンバーにアクセスしているだけのマクロですね。
それとアルゴリズムとして理解しておくと良いのが、双方向連結リストの要素削除です。
malloc.c(https://github.com/MacKomatsu/glibc/blob/release/2.27/master/malloc/malloc.c).
1403 /* Take a chunk off a bin list */ 1404 #define unlink(AV, P, BK, FD) { \ 1405 if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0)) \ 1406 malloc_printerr ("corrupted size vs. prev_size"); \ 1407 FD = P->fd; \ 1408 BK = P->bk; \ 1409 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \ 1410 malloc_printerr ("corrupted double-linked list"); \ 1411 else { \ 1412 FD->bk = BK; \ 1413 BK->fd = FD; \
unlink() マクロは以下のような処理をします。
これによりチャンク P を双方向連結リストから削除します。
Copyright 2018-2019, by Masaki Komatsu