Memory Allocation

1.Memory Mapping

We before learn about that,Virtual Address Space initially point disk(SSD, hard disk). if Page Fault causes disk's file data come up to Physical Memory in DRAM. this is called Regular File in Linux System

On the other hand, Sometimes we can use DRAM Memory as Disk. it is called Anonymous File(page).

void *mmap(void *start, size_t length, int prot, int flags,int fd, off_t offset);

Anonymous file(page) can allocated by mmap, seting fd set -1 and offset 0. operating simmilarly with disk, but not allocated in Physical Page yet. initializing all space with 0, If Read/Write executed, Anonymous file(page) is allocated to Physical memory. The key is, there is no transaction between disk and memory. also named as demand-zero pages

 

if you call execve("a.out",NULL,NULL) : 

.data .text , shared-libarary is filed-backed. As we know heap is using memory, heap is not file-backed, demand-zero file.

 

#include <unistd.h>
#include <sys/mman.h>
#include <stdio.h>
#include "../csapp.h"

void mmapcopy(int fd,int size)
{
    char* bufp;
    bufp=Mmap(NULL,size,PROT_READ,MAP_PRIVATE,fd,0);
    Write(1,bufp,size);
    return;
}

int main(int argc, char**argv){
    struct stat stat;
    int fd;
    if(argc!=2){
        printf("usage: %s <filename>\n",argv[0]);
        fd=Open(argv[1],O_RDONLY,0);
        fstat(fd,&stat);
        mmapcopy(fd,stat.st_size);
        exit(0);
    }
}

 

Shared Object

-Shared Object means Physical memory that used commonly by processes more than two. For example, C Library printf and Linux Bash shell, instead of copy same code area that is memory wasting, Processes share memory space of C Library and Linux Bash shell.

 

Private Object

Private Object starts as similar as Shared Object. Difference is, when other proccess try write on Private Object Area, Protection fault occurs. Since Private flagged as private copy-on-write, handler detect it and then it make copy of Private area in other project with write permission bit. Afther handler returns, Process(CPU) reexecutes write on newly created page. 

 

 

2.Memory Allocation

 

malloc allocate memory at runtime. malloc are abstracted function that call mmap or sbrk by size user wants to allocate.

#ifndef DEFAULT_MMAP_THRESHOLD_MIN
#define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
#endif

#ifndef DEFAULT_MMAP_THRESHOLD_MAX
  /* For 32-bit platforms we cannot increase the maximum mmap
     threshold much because it is also the minimum value for the
     maximum heap size and its alignment.  Going above 512k (i.e., 1M
     for new heaps) wastes too much address space.  */
# if __WORDSIZE == 32
#  define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
# else
#  define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
# endif
#endif

The critical point to system to which function to call, is MMAP_THRESHOLD. DEFAULT value is 128KB.(but my system,UBUNTU 18 says 131KB).

If size over 130KB, mmap function called and memory is allocated in Virtual Memory space in DRAM, as we know, not heap.

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

void program_break_test() {
  printf("%10p\n", sbrk(0));

  char *bl = malloc(131* 1024);//2*20, 1024KB
    printf("malloc'd at: %10p\n", bl);
  printf("sbrk : %10p\n", sbrk(0));
  printf("free : %p\n",bl);
  free(bl);
  printf("sbrk : %10p\n", sbrk(0));
}

int main(int argc, char **argv) {
  program_break_test();

  return 0;
}

0x5587c0530000
malloc'd at: 0x7f9271a0b010
0x5587c0551000
free : 0x7f9271a0b010
0x5587c0551000

 

Max size of memory allocating is same as DRAM size computer have.

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  void* a= malloc(sizeof(long)*1024*1024*1024*3);
  if(!a) printf("malloc failed\n");
  else printf("memory allocated\n");
  return 0;
}

If you have 16 GB DDR5 RAM, above would executed like below:

malloc failed

 

Under 130KB sbrk does works :

 

void* sbrk(intptr_r incr);

 

(b) double-word boundary : It is called Internal Fragmentation (after we talk). request payload was 5, but to keep double-word boundary, malloc pads extra block

 

Reason we have to use Dynamic Allocation:

There is program read files. file size is arbitary. If we define size of data structure, such as string, hard-coded size, As Input File get more bigger, maintenence could be difficult. If we define size small, program cannot execute. If not, huge size, program maintenence become nightmare.

 

Goals of Memory Allocation

constraints:

-Handling arbitary request sequence

-immediate response to request

-using only heap

-aligning blocks 

-not modifying  allocated blocks : allocater only manipulate or free free block, yet not allocated

 

1)Maximizing Throughput

- 500 malloc , 500 free request per second - > throughput= 1000 operation per second

 

2)Maximazing Memory Utilization

Pk= aggregate payload

H = Heap Size(nondecreasing)

 

 

Internal Fragmentation

As we already seen, Internal Fragementation is situation allocater allocate blocks more than request payload.

 

External Fragmentation

It is circumstance ,When request comes, total of free block size is bigger than payload but free block is not aligned.

so allocater needs to work to make small number of big block, rather than large number of small block.

 

 

3.Implementation

 

 

heap header

To distinguish free block and allocated, every block consist of heap header, whose size is one word(4byte)

and header include information about state of block.

So, Lets look at example to understand : 

malloc(2) -> header size 4+2 = 6 byte -> round up to double word constraint : 8 byte allocated

block header : 1000 |  1= 1001(0x9)

malloc(9) -> header size 4+9 = 13 byte -> round up to double world constraint : 16 byte allocated

block header : 10000 | 1 = 10001(0x11)

malloc(15) -> header size 4 + 15 = 19 byte -> round up to double world constraint : 24 byte allocated

block header : 11000 | 1 = 11001 = 0x19

malloc(2) : same as malloc(15)

 

 

placement policy

-first fit : search begins from first free block

-next fit : search begins from previous search left off

-best fit : find minimum size of free block

 

colealescing 

there is contiguous two 16/0 block. if next request payload is 4 word, memory allocation failed, which called false fragmentation. To avoid such circumstances, we have to merge small chopped free block, named as colealescing.

colealescing next block would be simple because of heap header. On the contrary, colealescing previous block spending time linear, traversing block until turn of header, is hard job.

Footer : Boundary Tag

As similar as heap header, Footer is good solution to it.

 

 

Explicit Free List

in Implicit Free List, It takes time linear proportionally to total size of block. Explicist Free list adopt double linked list of Free blocks, which take time constant or linear.

 

insertion of double link list can operate like LIFO(first fit), or address order.

 

 

1)Segregated Fits - GNU using

-All Allocaters maintains free list like above.

-search best fit of block ( optionally split, coleascing ) : Memory Utilization Improve

- possibilitiy of external/internal fragmentation

 

2)Buddy System

 

-Set Lower Limit of memory chunk(if not, memory waste to remember a lot of free or allocate space would occur).

above case, Limit is 6 (2^6=64K)

- when free exectue, recursively coleascing adjacent free block

t=1 allocate 35~64K A

t=2 allocate 65~128K B

t=3 allcoate 35~64K C

t=4 allocate 65~128K D

t=5 free C

t=6 free A

t=7 free B

t=8 free D