这次实验起初感觉书上就有答案，但是把书上的一点一点打上去之后看了大佬的博克，我就菜的睡不着了，这一章的最后一部分看的不认真，当时实在是头疼，急着看完去睡觉，结果错过了这次实验最重要的部分，分离空闲链表法，刚开始看到这个我以为就是维护一个存放空闲块的链表，因为不记得之前写ucore时候有这种优化方法，回过头又去看了遍书，感觉和我想的完全不一样，是我坐井观天了，这一算法就是维护多个链表，每个链表都是存放大小近似于一个值的空闲块，这样要分的话直接去对应的找就行，说最有匹配算法我觉得不为过。
其实只要理解这点就好办了，要求的四个函数书上都有实现，包括调用的find和place，只不过有些需要魔改一波，但是有个参照就相对容易得多，之后就是维护链表的操作，一个插入一个删除，当然还有求得在哪个链表的里对应函数。

defind参考书上给出的

mm_init

这个就开头那几行和书上不一样，主要是给链表分配了空间，堆的结构参考这里，

int mm_init(void)   //书上有类似实现
{
  if(heap_listp = mem_sbrk((MAX_LIST_NUM * sizeof(intptr_t)+4*WSIZE)==(void *)-1)
    return -1;

  // 将所有空闲链表的头指针初始为NULL
  for (int i = 0; i < MAX_LIST_NUM; ++i) {
      PUT_P(heap_listp + i * sizeof(intptr_t), NULL);
  }
  heap_listp += MAX_LIST_NUM * sizeof(intptr_t);

  PUT(heap_listp,0);
  PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
  PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
  PUT(heap_listp + (3*WSIZE), PACK(0, 1));

  if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
    return -1;
  return 0;
}

extend_heap

我写的和书上一样，插入链表部分我放到合并里了

static void *extend_heap(size_t words)
{
  char *bp;
  size_t size;

  size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
  if((long)(bp = mem_sbrk(size)) == -1)
    return NULL;

  PUT(HDRP(bp), PACK(size, 0));
  PUT(FTRP(bp), PACK(size, 0));
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  return coalesce(bp);
}

mm_malloc

和书上的一样,从链表删除放到place里了

void *mm_malloc(size_t size)            //书上的
{
	size_t align_size; 		/* Adjusted block size */
	size_t extendsize; 	/* Amount to extend heap if no fit */
	char *bp;

	/* Igore spurious requests */
	if (0 == size) {
		return NULL;
	}

	/* Adjusted block size to include overhead and alignment reqs */
	if (size <= DSIZE) {
		align_size = 2 * DSIZE;
	} else {
		align_size = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
	}

	/* Search the free list for a fit */
	if ((bp = find_fit(align_size)) != NULL) {
		place(bp, align_size);
		return bp;
	}

	/* No fit found. Get more memory and place the block */
	extendsize = MAX(align_size, CHUNKSIZE);
	if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
		return NULL;
	}
	place(bp, align_size);
	return bp;
}

mm_free

和书上一样

void mm_free(void *ptr)
{
  size_t size = GET_SIZE(HDRP(ptr));

  PUT(HDRP(ptr), PACK(size, 0));
  PUT(FTRP(ptr), PACK(size, 0));
  coalesce(ptr);
}

coalesce

和书上基本一样，加了一个加入链表环节

static void *coalesce(void *bp)
{
  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));

  if(prev_alloc && next_alloc)      //对应书上三种情况
    return bp;
  else if(prev_alloc && !next_alloc){
    size +=GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
  }
  else if(!prev_alloc && next_alloc){
    size +=GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
  }
  else{
    size += GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(FTRP(NEXT_BLKP(bp)));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
  }

	insert_list(bp);  //最后把空闲空间放回链表
  return bp;
}

mm_realloc

内存对齐和malloc一样，然后就是判断三种情况，第一种是要的空间太小，不需要再开
第二种 比原来大，但是原来的加上相邻块一起比所需大，就合并下一块然后返回
第三种，加上附近空闲的也不够，只能把原来的free了，再重新malloc

void *mm_realloc(void *ptr, size_t size)
{
	size_t align_size;
	void *oldptr = ptr;
	void *newptr;

	if ( size == 0) {
		free(oldptr);
		return NULL;
	}
  //数据对齐
	if (size <= DSIZE) {
		align_size = 2 * DSIZE;
	} else {
		align_size = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
	}
	if (align_size == GET_SIZE(HDRP(oldptr))) {
		return oldptr;
	}
  //可以用相邻空闲空间加上原本的
  size_t next_size=GET_SIZE(HDRP(NEXT_BLKP(oldptr)));
  size_t old_size=GET_SIZE(HDRP(oldptr))
  int next_alloc=GET_ALLOC(HDRP(NEXT_BLKP(oldptr)));
	if (!next_alloc && align_size < old_size+next_size) {
    delete_list(NEXT_BLKP(oldptr));
		newptr = oldptr;
    PUT(HDRP(newptr), PACK(next_size + old_size, 1));
    PUT(FTRP(newptr), PACK(next_size + old_size, 1));
		return newptr;
	}

	/* 从heap的其他地方寻找 */
	newptr = mm_malloc(size);
	if (NULL == newptr)
		return NULL;
	memmove(newptr, oldptr, size);
	mm_free(oldptr);

	return newptr;
}

place

照着书写，该删，该加的填上，ucore上以前做时候是大于两倍才分两半

static void *place(void *bp, size_t size) {
    int max_size = GET_SIZE(HDRP(bp));
    int delta_size = max_size - size;
    delete_list(bp);
    // 如剩余部分少于最小块大小, 不做分割，在ucore中是不到两倍不分割
    if (delta_size < 2*DSIZE) {
        PUT(HDRP(bp), PACK(max_size, 1));
        PUT(FTRP(bp), PACK(max_size, 1));
        return bp;
    }

    // 否则需要分割，并将分割后的空闲块加到空闲链表
    PUT(HDRP(bp), PACK(size, 1));
    PUT(FTRP(bp), PACK(size, 1));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(delta_size, 0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(delta_size, 0));
		insert_list(bp);
    return bp;
}

find_fit

那些个链表找到最合适大小的，那个链表空就退而求其次

void *find_fit(size_t size)   //找到合适大小空闲空间
{
	int index;
	index = getListOffset(size);
	unsigned int *ptr;

	/* 最合适的空闲链表没有满足要求到空闲块就到下一个空闲链表寻找*/
	while (index < 18) {
		ptr = GET_PTR(heap_listp + 4 * index);
		while (ptr != NULL) {
			if (GET_SIZE(HDRP(ptr)) >= size) {
				return (void *)ptr;
			}
			ptr = GET_PTR(ptr);
		}
		index++;
	}
	return NULL;
}

insert_list 和 delete_list

参考的别人的，逻辑很清晰就是有些地方比较繁琐，赶紧写完玩去

void insert_list(void *bp)
{
	int index;
	size_t size;
	size = GET_SIZE(HDRP(bp));
	index = getListOffset(size);
    /*当前链表表头指向NULL*/
	if (GET_PTR(heap_listp + WSIZE * index) == NULL) {
		PUT_PTR(heap_listp + WSIZE * index, bp);
		PUT_PTR(bp, NULL);
		PUT_PTR((unsigned int *)bp + 1, NULL);
	} else {    /*当前链表已经有元素，插入到该链表表头，新的第一个元素与原来第一个元素连接*/
		PUT_PTR(bp, GET_PTR(heap_listp + WSIZE * index));
		PUT_PTR(GET_PTR(heap_listp + WSIZE * index) + 1, bp);  	
    	PUT_PTR((unsigned int *)bp + 1, NULL);
		PUT_PTR(heap_listp + WSIZE * index, bp);
	}
}

void delete_list(void *bp)
{
    int index;
    size_t size;
    size = GET_SIZE(HDRP(bp));
    index = getListOffset(size);
    if (GET_PTR(bp) == NULL && GET_PTR((unsigned int *)bp + 1) == NULL) { 
        /* 后继next为NULL，前驱prev也为NULL,表明这个链表仅含一个结点。
        然后我们将合适大小对应的头指针设置为NULL*/
        PUT_PTR(heap_listp + WSIZE * index, NULL);
    } else if (GET_PTR(bp) == NULL && GET_PTR((unsigned int *)bp + 1) != NULL) {
        /*当前链表有多个结点，是最后一个。
        通过prev指针得到前一个块，再减去(unsigned int)1，就得到了指向next的指针，
        再将next指向NULL*/
        PUT_PTR( (GET_PTR( (unsigned int*)GET_PTR((unsigned int *)bp + 1) - 1 )), NULL );
        PUT_PTR(GET_PTR((unsigned int *)bp + 1), NULL);  //bp前驱指针prev=NULL
    } else if (GET_PTR(bp) != NULL && GET_PTR((unsigned int *)bp + 1) == NULL){
        /*当前链表有多个结点，是第一个
        第一条语句将相应大小的头指针指向了bp的next*/
        PUT_PTR(heap_listp + WSIZE * index, GET_PTR(bp));
        PUT_PTR(GET_PTR(bp) + 1, NULL); //prev=NULL
    } else if (GET_PTR(bp) != NULL && GET_PTR((unsigned int *)bp + 1) != NULL) {
        /*当前链表有多个节点，为中间结点
        第一条前一个块的next指向了当前块的next*/
        PUT_PTR(GET_PTR((unsigned int *)bp + 1), GET_PTR(bp));
        PUT_PTR(GET_PTR(bp) + 1, GET_PTR((unsigned int*)bp + 1));//bp->prev = bp->next
    }
}

getListOffset

参考别人的小技巧，switch也可以

int getListOffset(size_t size)
{
	if (size <= (1<<4)) {
		return 0;
	} else if (size <= (1<<5)) {
		return 1;
	} else if (size <= (1<<6)) {
		return 2;
	} else if (size <= (1<<7)) {
		return 3;
	} else if (size <= (1<<8)) {
		return 4;
	} else if (size <= (1<<9)) {
		return 5;
	} else if (size <= (1<<10)) {
		return 6;
	} else if (size <= (1<<11)) {
		return 7;
	} else if (size <= (1<<12)) {
		return 8;
	} else if (size <= (1<<13)) {
		return 9;
	} else if (size <= (1<<14)) {
		return 10;
	} else if (size <= (1<<15)) {
		return 11;
	} else if (size <= (1<<16)) {
		return 12;
	} else if (size <= (1<<17)) {
		return 13;
	} else if (size <= (1<<18)) {
		return 14;
	} else if (size <= (1<<19)) {
		return 15;
	} else if (size <= (1<<20)) {
		return 16;
	} else {
		return 17;
	}
}

虽然只是一个malloc和free但是让我感觉和当时写ucore内存管理内容很相似，小小一个实验，实现看似简单的函数，但是实际内容让人收益匪浅，这些实验真是很难得