segregate - first_fit

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 *
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"

#include <limits.h>

#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#define WSIZE       4       /* Word and header/footer size (bytes) */
#define DSIZE       8       /* Double word size (bytes) */
#define CHUNKSIZE   (1<<12) /* Extend heap by this amount (bytes) */

#define MAX(x, y) ((x) > (y)? (x) : (y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p)      (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)    ((char *)(bp) - WSIZE)
#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* Pointers to predecessor and successor in free list */
#define PREDP(bp) (*(void **)(bp))
#define SUCCP(bp) (*(void **)(bp + WSIZE))

/* --- Segregated List Defines --- */
#define NUM_CLASSES 20  /* Number of size classes */

typedef void * (*fit_policy_t)(size_t asize);

/* --- Global Variables --- */
static char *free_lists[NUM_CLASSES]; /* Array of segregated list heads */
static char *heap_listp;              /* Pointer to prologue block */

/* --- Function Prototypes --- */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize, fit_policy_t fit_policy);
static void *segregated_first_fit(size_t asize);
static void place(void *bp, size_t asize);
static void list_add(void *bp);
static void list_remove(void *bp);
static int get_list_index(size_t size);

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) -1)
        return -1;

    PUT(heap_listp, 0);                         /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));     /* Epilogue header */
    heap_listp += (2 * WSIZE);

    /* Initialize all segregated list heads to NULL */
    for (int i = 0; i < NUM_CLASSES; i++) {
        free_lists[i] = NULL;
    }

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

/*
 * mm_malloc - Allocate a block.
 */
void *mm_malloc(size_t size) {
    size_t asize; /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

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

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

/*
 * mm_free - Freeing a block.
 */
void mm_free(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));

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

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
 void *mm_realloc(void *ptr, size_t size) {
     void *oldptr = ptr;
     void *newptr;

     if (size == 0) {
         mm_free(ptr);
         return NULL;
     }

     if (ptr == NULL) {
         return mm_malloc(size);
     }

     newptr = mm_malloc(size);
     if (newptr == NULL)
         return NULL;

     size_t copysize = GET_SIZE(HDRP(ptr)) - DSIZE;
     if (size < copysize) {
         copysize = size;
     }
     memcpy(newptr, oldptr, copysize);
     mm_free(oldptr);
     return newptr;
}

/*
 * extend_heap - Extends the heap with a new free block.
 */
static void *extend_heap(size_t words) {
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long) (bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
    PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

/*
 * list_add - Add a free block to the appropriate size class list.
 * Uses LIFO (Last-In, First-Out) insertion.
 */
static void list_add(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int index = get_list_index(size);

    void *list_head = free_lists[index];

    PREDP(bp) = NULL;
    SUCCP(bp) = list_head;
    if (list_head != NULL) {
        PREDP(list_head) = bp;
    }

    free_lists[index] = bp;
}

/*
 * list_remove - Remove a block from its size class list.
 */
static void list_remove(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int index = get_list_index(size);

    void *pred_bp = PREDP(bp);
    void *succ_bp = SUCCP(bp);

    if (pred_bp == NULL && succ_bp == NULL) {
        /* Only block in list */
        free_lists[index] = NULL;
    } else if (pred_bp == NULL) {
        /* Head of list */
        PREDP(succ_bp) = NULL;
        free_lists[index] = succ_bp;
    } else if (succ_bp == NULL) {
        /* Tail of list */
        SUCCP(pred_bp) = NULL;
    } else {
        /* Middle of list */
        SUCCP(pred_bp) = succ_bp;
        PREDP(succ_bp) = pred_bp;
    }
}

/*
 * coalesce - Merge adjacent free blocks.
 */
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) {
        /* Case 1: Both allocated. No merge. */
    } else if (prev_alloc && !next_alloc) {
        /* Case 2: Next block is free. */
        list_remove(NEXT_BLKP(bp));
        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) {
        /* Case 3: Previous block is free. */
        list_remove(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    } else {
        /* Case 4: Both previous and next are free. */
        list_remove(PREV_BLKP(bp));
        list_remove(NEXT_BLKP(bp));
        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);
    }

    /* Add the (potentially new, larger) block to the correct list */
    list_add(bp);
    return bp;
}

/*
 * segregated_first_fit - Find a fit in the segregated lists.
 * Searches from the block's size class up to larger classes.
 */
static void *segregated_first_fit(size_t asize) {
    int index = get_list_index(asize);
    void *bp;

    /* Search from the correct size class upwards */
    for (int i = index; i < NUM_CLASSES; i++) {
        for (bp = free_lists[i]; bp != NULL; bp = SUCCP(bp)){
            if (asize <= GET_SIZE(HDRP(bp))) {
                return bp;
            }
        }
    }

    return NULL; /* No fit found */
}

/*
 * find_fit - Wrapper for the chosen fit policy.
 */
static void *find_fit(size_t asize, fit_policy_t fit_policy) {
    return fit_policy(asize);
}

/*
 * place - Place block in heap, splitting if large enough.
 */
static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    list_remove(bp); /* Remove this block from its free list */

    if ((csize - asize) >= (2 * DSIZE)) {
        /* Split the block */
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        /* Add the remaining fragment back to the free list */
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
        list_add(bp);
    } else {
        /* Do not split */
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/*
 * get_list_index - Given a block size, return the correct
 * size class list index.
 */
static int get_list_index(size_t size) {
    /* * Simple power-of-2 size classes.
     * 0: [1, 32]
     * 1: [33, 64]
     * 2: [65, 128]
     * ...
     * 19: [2^20+1, infinity]
     */
    if (size <= 32) return 0;
    if (size <= 64) return 1;
    if (size <= 128) return 2;
    if (size <= 256) return 3;
    if (size <= 512) return 4;
    if (size <= 1024) return 5;
    if (size <= 2048) return 6;
    if (size <= 4096) return 7;
    if (size <= 8192) return 8;
    if (size <= 16384) return 9;
    if (size <= 32768) return 10;
    if (size <= 65536) return 11;
    if (size <= 131072) return 12;
    if (size <= 262144) return 13;
    if (size <= 524288) return 14;
    if (size <= 1048576) return 15;
    if (size <= 2097152) return 16;
    if (size <= 4194304) return 17;
    if (size <= 8388608) return 18;

    /* All larger blocks go in the last list */
    return 19;
}

CSAPP 8.6 ~ 8.8

8.6 비지역 점프 (Nonlocal Jumps)

C 언어는 비지역 점프(nonlocal jump)라는 사용자 수준의 예외적 제어 흐름(ECF)을 제공합니다. 이는 일반적인 함수 호출/반환 순서를 무시하고, 한 함수에서 스택 상의 다른 (현재 실행 중인) 함수로 제어권을 직접 이전시키는 기능입니다. 이 기능은 setjmp와 longjmp 함수를 통해 제공됩니다.

---

1. setjmp와 longjmp의 동작 원리

setjmp / sigsetjmp

#include <setjmp.h>

int setjmp(jmp_buf env);
int sigsetjmp(sigjmp_buf env, int savesigs);

• 역할: 현재 호출 환경(프로그램 카운터, 스택 포인터, 레지스터 등)을 env 버퍼에 저장합니다.
• 반환 (특이점): setjmp는 여러 번 반환될 수 있습니다.
  1. 최초 호출 시: 0을 반환합니다.
  2. longjmp를 통해 복귀 시: longjmp가 전달한 0이 아닌 값(retval)을 반환합니다.
• 주의: setjmp의 반환 값은 rc = setjmp(env);처럼 변수에 할당해서는 안 되며, switch나 if 조건문에서만 안전하게 사용할 수 있습니다.

longjmp / siglongjmp

#include <setjmp.h>

void longjmp(jmp_buf env, int retval);
void siglongjmp(sigjmp_buf env, int retval);

• 역할: env 버퍼에 저장된 환경을 복원하고, 가장 최근에 env를 저장했던 setjmp 호출 지점으로 즉시 점프합니다.
• 반환 (특이점): longjmp는 longjmp를 호출한 위치로 절대 반환하지 않습니다(Never returns).

---

2. 활용 1: 깊은 중첩에서의 에러 처리 (Fig 8.43)

longjmp의 가장 중요한 용도는, 깊게 중첩된 함수(main $\rightarrow$ foo $\rightarrow$ bar)에서 에러가 발생했을 때, 스택을 일일이 return으로 거슬러 올라가지 않고 에러 핸들러로 즉시 탈출하는 것입니다.

• 예시 (Fig 8.43):
  1. main이 setjmp(buf)를 호출하여 복귀 지점(case 0)을 설정합니다.
  2. main이 foo()를 호출하고, foo()가 bar()를 호출합니다.
  3. bar()에서 error2가 감지되면, longjmp(buf, 2)를 호출합니다.
  4. 제어권은 foo()를 건너뛰고 main의 setjmp 위치로 즉시 점프합니다.
  5. setjmp는 longjmp가 보낸 2를 반환하고, switch문이 case 2를 실행하여 에러를 처리합니다.
• ⚠️ 경고: 메모리 누수 longjmp는 foo 같은 중간 함수를 강제로 건너뜁니다. 만약 foo 함수가 malloc으로 메모리를 할당하고 함수 마지막에 free를 하도록 설계되었다면, 이 free 코드가 실행되지 않아 메모리 누수가 발생할 수 있습니다.
  

---

3. 활용 2: 시그널 핸들러에서 분기 (Fig 8.44)

longjmp는 시그널 핸들러가 중단된 코드로 복귀하는 대신, 프로그램의 특정 지점(예: 시작점)으로 분기할 수 있게 합니다. (예: Ctrl+C로 프로그램 재시작)

• sigsetjmp / siglongjmp: 시그널 핸들러에서 안전하게 사용하기 위한 특별한 버전입니다. setjmp/longjmp의 기능에 더해 시그널 컨텍스트(예: 시그널 차단 벡터)까지 저장하고 복원합니다.
  
• 예시: main이 sigsetjmp로 재시작 지점을 저장합니다. Ctrl+C (SIGINT) 시그널이 발생하면, 핸들러가 siglongjmp를 호출하여 main의 시작 지점으로 제어를 되돌려 프로그램을 "재시작"합니다.

---

4. siglongjmp 사용 시 중요 주의사항

1. 경합 상태 (Race Condition):

   반드시 sigsetjmp를 먼저 호출하여 복귀 지점을 설정한 후에, Signal로 핸들러를 설치해야 합니다. (그렇지 않으면 핸들러가 sigsetjmp보다 먼저 실행될 수 있음)

2. 비동기-시그널-안전 (Async-Signal-Unsafe):

   siglongjmp는 시그널-안전 함수가 아닙니다. 따라서 siglongjmp가 되돌아간 지점(즉, sigsetjmp가 0이 아닌 값을 반환한 직후)부터는 sio_puts나 sleep처럼 시그널-안전이 보장된 함수들만 호출해야 합니다.

8.7 프로세스 조작을 위한 도구들

리눅스 시스템은 프로세스를 모니터링하고 조작하기 위한 여러 유용한 도구들을 제공합니다.

• strace:
  • 실행 중인 프로그램과 그 자식들(children)이 호출하는 모든 시스템 콜(system call)을 추적하여 출력합니다.
  • 호기심 많은 학생에게 아주 흥미로운(fascinating) 도구입니다.
  • (공유 라이브러리 관련 잡다한 출력 없이) 더 깔끔한 추적 결과를 얻으려면, 프로그램을 static 플래그와 함께 컴파일하는 것이 좋습니다.
• ps:
  • 현재 시스템에 있는 프로세스들(좀비 프로세스 포함)의 목록을 보여줍니다.
• top:
  • 현재 프로세스들의 리소스 사용량에 대한 정보를 출력합니다.
• pmap:
  • 프로세스의 메모리 맵을 표시합니다.
• /proc:
  • 수많은 커널(kernel) 자료 구조의 내용을 ASCII 텍스트 형태로 내보내는(export) 가상 파일 시스템(virtual filesystem)입니다.
  • 사용자 프로그램은 이 텍스트 파일들을 읽을 수 있습니다.
  • 예시: 터미널에 cat /proc/loadavg를 입력하면, 리눅스 시스템의 현재 "로드 애버리지(load average)"를 볼 수 있습니다.

8.8 요약 (Summary)

• 예외적 제어 흐름(ECF)은 컴퓨터 시스템의 모든 수준에서 발생하며, 시스템에 동시성(concurrency)을 제공하는 기본 메커니즘입니다.
• 하드웨어 수준:
  • 예외(Exception)는 프로세서 내부 이벤트에 의해 트리거되는 제어 흐름의 갑작스러운 변경입니다.
  • 제어 흐름은 소프트웨어 핸들러로 전달되며, 핸들러는 일부 처리를 수행한 뒤 중단된 제어 흐름으로 제어를 반환합니다.
• 4가지 예외 유형:
  • 인터럽트 (Interrupts):
    • 타이머 칩이나 디스크 컨트롤러 같은 외부 I/O 장치가 프로세서의 인터럽트 핀을 설정할 때 비동기적으로 발생합니다.
    • 제어는 장애를 일으킨 명령어(faulting instruction) 다음의 명령어로 돌아갑니다.
  • 폴트 (Faults)와 중단 (Aborts):
    • 명령어 실행의 결과로 동기적으로 발생합니다.
    • 폴트 핸들러는 장애를 일으킨 명령어를 재시작시킵니다.
    • 중단 핸들러는 중단된 흐름으로 제어를 절대 반환하지 않습니다.
  • 트랩 (Traps):
    • 시스템 콜(System Call)을 구현하는 데 사용되는 함수 호출과 유사하며, 애플리케이션이 OS 코드로 진입하는 제어된 통로를 제공합니다.
• 운영체제(OS) 수준:
  • 커널은 ECF를 사용하여 프로세스(process)라는 기본 개념을 제공합니다.
  • 프로세스는 애플리케이션에 두 가지 중요한 추상화(abstraction)를 제공합니다.
    1. 논리적 제어 흐름: 각 프로그램이 프로세서를 독점적으로 사용하는 듯한 환상을 줍니다.
    2. 사적 주소 공간: 각 프로그램이 주 메모리를 독점적으로 사용하는 듯한 환상을 줍니다.
• OS와 애플리케이션 인터페이스:
  • 애플리케이션은 자식 프로세스를 생성하고, 자식 프로세스가 멈추거나 종료되기를 기다리고(wait), 새 프로그램을 실행하며, 다른 프로세스로부터 시그널(signal)을 받을 수 있습니다.
  • 시그널 처리의 의미는 미묘하며 시스템마다 다를 수 있지만, Posix 호환 시스템에는 예상되는 시그널 처리 의미를 명확히 지정하는 메커니즘이 존재합니다.
• 애플리케이션 수준:
  • C 프로그램은 비지역 점프(nonlocal jump) (setjmp, longjmp)를 사용하여 일반적인 호출/반환 스택 규율을 우회하고 한 함수에서 다른 함수로 직접 분기(branch)할 수 있습니다.