# 1.Large bin

# 1.

在释放堆块时，想要进入large bin的堆块需要大于等于512（1024）字节【用户空间需要大于等于0x3F0，用户空间小于0x3F0进入small bin】

而largebin还要考虑fd_nextsiez和bk_nextsize，这两个是因为，在largebin中，会按着相同大小的chunk归到一起，不同chunk组直接的联系就需要fd_nextsize和bk_nextsize。这里除了每组的第一个chunk ，其他的fd_nextsize和bk_nextsize 都为0

fd_nextsize指向了下一组的第一个chunk
bk_nextsize指向了上一组的第一个chunk

# 2.结构：

large chunk在fd的遍历顺序为从大到小【图中szie大小为 1>2>3，相同组号的size相同（1-1，1-2，1-3相同）】

【自己画完才发现别人的（自己画的应该有误）】

原地址：https://www.cnblogs.com/hyq2/p/15998570.html

# 3.插入顺序：

插入位置按照大小，从大到小排序（小的连接large bin块）
大小相同按照free时间排序
多个大小相同的堆块，只有首堆块的fd_nextsize和bk_nextsize会指向其他堆块，后面的堆块的fd_nextsize和bk_nextsize均为0
size最大的chunk的bk_nextsize指向最小的chunk，size最小的chunk的fd_nextsize指向最大的chunk

# 2.原理：

# 1.我自己的理解：

由于在largebin中插入chunk时会按照大小排序，这就给了我们机会去在比大小时作手脚；

# 在`glibc2.23`中`malloc.c`文件中，比较过程如下：

while((unsigned long) size< fwd->size){ //这里size为新插入的，fwd为已经在largebin中的 前一个刚释放  的chunk
	fwd=fwd->fd_nextsize;
	assert((fwd->size & NON_MAIN_ARENA) == 0);
}

在largebin中的chunk如果index相同的情况下，是按照从小到大的顺序排列的，也就是说在index相同的情况下size越小的chunk，越接近largebin(fd指向largebin,与图对应)，上面的代码是比较新插入的chunk的size(size)是否小于上一个刚释放进入largebin中的chunk的size(fwd_size) 的过程

当小于成立时，执行while中的流程；不成立时，判断：

if ( (unsigned long) size == (unsigned long) fwd->size)
//Always insert in the second position
	fwd=fwd->fd;

上面的这个对我们来说无法利用，接下来判断大于时：

else
	{
	  victim->fd_nextsize = fwd;                     //victim是当前新插入的chunk
	  victim->bk_nextsize = fwd->bk_nextsize; //fwd是前一个释放的chunk
	  fwd->bk_nextsize = victim;//将前一个释放的bk_nextsize指向新的chunk
	  victim->bk_nextsize->fd_nextsize = victim;//修改新的chunk的上一个大小不相同的chunk的fd_nextsize指向自己
	}
	bck = fwd ->bk; //bck为上一个释放的chunk的bk

上面这一段我们可以进行利用，当我们对fwd的内容进行修改后，改变其bk和bk_nextsize的指向然后在执行上面这一段代码就会将一些值改变：

1.选择两个地址为我们想要修改的值的地址：

这里选择stack1和stack2

2.然后修改fwd的值(fwd为上一个释放的large_chunk):

3.修改完后就会变成如下情况：

4.再当执行上面判断大小结果为大于的时候的代码时：

else
	{
	  victim->fd_nextsize = fwd;                     //victim是当前新插入的chunk
	  victim->bk_nextsize = fwd->bk_nextsize; //fwd是前一个释放的chunk
	  fwd->bk_nextsize = victim;//将前一个释放的bk_nextsize指向新的chunk
	  victim->bk_nextsize->fd_nextsize = victim;//修改新的chunk的上一个大小不相同的chunk的fd_nextsize指向自己
	}
	bck = fwd ->bk; //bck为上一个释放的chunk的bk

将victim插入时发现

victim->bk_nextsize->fd_nextsize = victim;
//victim-bk_nextsize已经指向了fake_chunk2
//这里就将fake_chunk2的fd_nextsize的值变为了victim的地址，也就将stack2原来的值变为了victim的地址

5.修改stack1的值

在执行完对victim和fwd的fd_nextsize和bk_nextsize的修改后，会继续对他俩的fd和bk修改

mark_bin(av,victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;  //bck为fwd的bk指针

这里会发现：

bck->fd = victim;
//这里bck = fwd -> bk
//也就等于 fwd->bk->fd = victim
//就将fack_chunk1的 stack（fd）的值改为了 victim 的地址

最后我们就将

fake_chunk1的fd（stack1）的值改为了victim的地址
fake_chunk2的fd（stack2）的值改为了victim的地址

# Large bin的利用条件：

可以修改一个large bin chunk的data域（fwd的bk和bk_nextsize）
从unsorted bin 中来的large bin chunk（victim）要紧跟在被构造过的chunk(fwd)后面【为了判断大小时能够插入到正确的地方】

# 在malloc.c中从unsorted bin去将chunk放入对应的bin（large bin）的完整代码：

          /* remove from unsorted list */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

          /* Take now instead of binning if exact fit */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size);
              if (av != &main_arena)
                victim->size |= NON_MAIN_ARENA;
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }

          /* place chunk in bin */

          if (in_smallbin_range (size))
            {
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
            }
          else
            {
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              /* 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 ((unsigned long) (size) < (unsigned long) (bck->bk->size))
                    {
                      fwd = bck;
                      bck = bck->bk;

                      victim->fd_nextsize = fwd->fd;
                      victim->bk_nextsize = fwd->fd->bk_nextsize;
                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                    }
                  else
                    {
                      assert ((fwd->size & NON_MAIN_ARENA) == 0);
                      while ((unsigned long) size < fwd->size)
                        {
                          fwd = fwd->fd_nextsize;
                          assert ((fwd->size & NON_MAIN_ARENA) == 0);
                        }

                      if ((unsigned long) size == (unsigned long) fwd->size)
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                      else
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                    }
                }
              else
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

          mark_bin (av, victim_index);
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;