Dynamic Memory Management

  

Dynamic Memory Management


Stack

Heap

BSS

Data

RoData

Text

What do malloc() and free() do?

Memory Layout: Heap



ü Needed when required memory size is not known before the program runs

Allocating & Deallocating Memory

§  Dynamically allocating memory

ü Programmer explicitly requests space in memory

ü Space is allocated dynamically on the heap

ü E.g., using “malloc” in C, and “new” in Java

§  Dynamically deallocating memory

ü Must reclaim or recycle memory that is never used again

ü To avoid (eventually) running out of memory

 

§  “Garbage”

ü Allocated block in heap that will not be accessed again

ü Can be reclaimed for later use by the program

 

Option #1: Garbage Collection

§  Run-time system does garbage collection (Java)

§  Automatically determines objects that canʼt be accessed

§  And then reclaims the resources used by these object 

 easy

•     “if (complex_function(y))  x = Quux();”

•     Run-time system cannot collect all of the garbage

1.    Detecting the garbage introduces overhead

•     Keeping track of references to objects (e.g., counter)

•     Scanning through accessible objects to identify garbage

•     Sometimes walking through a large amount of memory

2.    Cleaning the garbage leads to bursty delays

a.    E.g., periodic scans of the objects to hunt for garbage

b.   Leading to unpredictable “freeze” of the running program

c.    Very problematic for real-time applications … though good run-time systems avoid long freezes

 Option #2: Manual Deallocation

Ø Programmer deallocates the memory (C and C++)

•     Manually determines which objects canʼt be accessed

•     And then explicitly returns the resources to the heap

•     E.g., using “free” in C or “delete” in C++

Ø Advantages

•     Lower overhead

•     No unexpected “pauses”

•     More efficient use of memory

Ø Disadvantages

•     More complex for the programmer

•     Subtle memory-related bugs

•     Security vulnerabilities in the (buggy) code

Manual Deallocation can lead to bugs.

Ø Dangling Pointer

ü Programmer frees a region of memory

ü … but still has a pointer to it

ü  Dereferencing pointer reads or writes nonsense values

int main(void) { char *p;

p = malloc(10);

… free(p);

… putchar(*p);

}

May print

nonsense character.

9


 

 

 

Manual Deallocation Can Lead to Bugs:

Ø  Memory Leak

ü Programmer neglects to free unused region of memory

ü So, the space can never be allocated again

ü Eventually may consume all the available memory

 

void f(void){

          char *s;

          s = malloc(50);

          return;

}

 

int main(void){

          while(1)f();

          return 0;

}

Eventually malloc() returns NULL



 

                                                     

 

 

 

 

 

 

 

 

 

 

 

Manual Deallocation Can Lead to Bugs

Ø Double Free

ü Programmer mistakenly frees a region more than once

ü Leading to corruption of the heap data structure

ü … or premature destruction of a different object

 

int main(void){

          char *p, *q;

          p = malloc(10);

          …

          free(p);

          q=malloc(10);

          free(p);

          …

}

 

 

                                                                                                                                 

Might free the space allocated to q

                                                                                                                                      

 

 

 

 

 

 

Ø Malloc() and calloc() challenges

ü malloc() may ask for arbitrary number of bytes

ü Memory may be allocated & freed in different order

ü Cannot reorder requests to improve performance

char *p1 = malloc(3);

char *p2 = malloc(1);

char *p3 = malloc(4);

free(p2);

char *p4 = malloc(6);

free(p3);

char *p5 = malloc(2);

free(p1);

free(p4);

free(p5);

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


How do malloc() and free() work?

 

The Program Break:

The program break marks the boundary between heap and stack

 

Heap

 

 

Stack

 

 

Program break

00000000

FFFFFFFF

 

 

 

 


         

      Initially the stack has maximum size  

 

 

 

 

Stack

 

 

Program break

00000000

FFFFFFFF

 

 

 

 

 


Acquiring Heap Memory

 

Q:  How does malloc() acquire heap memory?

A:  Moves program break downward via sbrk() or brk()

system call

void *sbrk(intptr_t increment);

§  Increment the program break by the specified amount. Calling the function with an increment of 0 returns the current location of the program break. Return 0 if successful and -1 otherwise.

§  Beware: On Linux contains a known bug; should call only with argument 0.

int brk(void *newBreak);

§  Move the program break to the specified address. Return 0 if successful and -1 otherwise.

Q:  Having acquired heap memory, how do malloc() and free() manipulate it?

A:  Topic of much research; an introduction…

Goals for malloc() and free()

§  Maximizing throughput

ü Maximize number of requests completed per unit time

ü Need both malloc() and free() to be fast

§  Maximizing memory utilization

ü Minimize the amount of wasted memory

ü Need to minimize size of data structures

§  Strawman #1: free() does nothing

ü Good throughput, but poor memory utilization

§  Strawman #2: malloc() finds the “best fit”

ü Good memory utilization, but poor throughput

Keeping Track of Free Blocks

§  Maintain a list of free blocks of memory

•   Allocate memory from one of the blocks in the free list

•   Deallocate memory by returning the block to the free list

•  When necessary, call brk() to ask OS for additional memory, and create a new large block

§  Design questions

•   How to keep track of the free blocks in memory?

•   How to choose an appropriate free block to allocate?

•   What to do with the left-over space in a free block?

•   What to do with a block that has just been freed?

 

 

free

 

free

 

free

 

 

 

Need to Minimize Fragmentation

 

§  Internal fragmentation

•   Allocated block is larger than malloc() requested

•   E.g., malloc() imposes a minimum size (e.g., 64 bytes)

 

 

 

33

 

 

 

 

 

§  External fragmentation

•   Enough free memory exists, but no block is big enough

•   

 
E.g., malloc() asks for 128 contiguous bytes

 

64

 

64

 

64

 


Simple “K&R-Like” Approach

ü Memory allocated in multiples of a base size

o   E.g., 16 bytes, 32 bytes, 48 bytes, …

ü Linked list of free blocks

o             malloc() and free() walk through the list to allocate and deallocate

ü malloc() allocates the first big-enough block

o   To avoid sequencing further through the list

ü malloc() splits the free block

o   To allocate what is needed, and leave the rest available

ü Linked list is circular

o   To be able to continue where you left off

ü Linked list in the order the blocks appear in memory

o   To be able to “coalesce” neighboring free blocks

 

Allocate Memory in Multiples of Base Size

•         Allocate memory in multiples of a base size

ü Avoid maintaining very tiny free blocks

ü Align memory on size of largest data type (e.g., double)

•         Requested size is “rounded up”

ü Allocation in units of base_size

ü Round:(nbytes + base_size – 1)/base_size

•         Example:

ü Suppose nbytes is 37

ü And base_size is 16 bytes

ü Then (37 + 16 – 1)/16 is 52/16 which rounds down to 3

16

16

5

 

 

 

 

 


Linked List of Free Blocks

•         Linked list of free blocks

•         malloc() allocates a big-enough block

 

 

 


 

 

Allocated


 

•        

Newly freed
free() adds newly-freed block to the list

 


 

“First-Fit” Allocation

•         Handling a request for memory (e.g., malloc())

ü Find a free block that satisfies the request

ü Must have a “size” that is big enough, or bigger

•         Simplest approach: first fit

ü Sequence through the linked list

ü Stop upon encountering a “big enough” free block

•         Example: request for 64 bytes

ü First-fit algorithm stops at the 128-byte block

48

32

64

128

256

 

 

 

 

 

Splitting an Oversized Free Block

 

•         Simple case: perfect fit

ü malloc() asks for 128 bytes, free block has 128 bytes

ü Simply remove the free block from the list

 


48

 

 


 64

 

            256

 

•         Complex case: splitting the block

ü malloc() asks for 64 bytes, free block has 128 bytes

 

                 32

64

48

 

64

64

256


 

 

 

 


Circular Linked List of Free Blocks

ü Advantages of making free list a circular list

•     Any element in the list can be the beginning

•     Donʼt have to handle the “end” of the list as special

ü Performance optimization

•     Make the head be where last block was found

•     More likely to find “big enough” blocks later in the list

 

256

64

64

48

32

 

 

 

 

 

 

Maintaining Free Blocks in Order

•         Keep list in order of increasing addresses

ü Makes it easier to coalesce adjacent free blocks

•         Though, makes calls to free() more expensive

ü Need to insert the newly-freed block in the right place

 

 

In use

 

 

In use

 

 

In use

 


Coalescing Adjacent Free Blocks

•         When inserting a block in the free list

ü “Look left” and “look right” for neighboring free blocks

 

 

 

 


In use

 

 

In use

 

“Left”

 

In use

 

“Right”

 

 

 

 

 

 


In use

 

 

In use

 

 

 

Conclusion

•         Elegant simplicity of K&R malloc() and free()

ü Simple header with pointer and size in each free block

ü Simple circular linked list of free blocks

ü Relatively small amount of code (~25 lines each)

•         Limitations of K&R functions in terms of efficiency

ü malloc() requires scanning the free list

•     To find the first free block that is big enough

ü free() requires scanning the free list

•     To find the location to insert the to-be-freed block



                                                                                    by

                                                    Thiru prashad G S  23USC004

                                                    Enoch jousva E        23US013

Comments

Post a Comment

Popular posts from this blog

ETHICAL HACKING - WHITE HAT HACKER

                                                             ETHICAL HACKING -  WHITE HAT TECHNIQUES A white hat hacker, also known as an ethical hacker, is a cybersecurity professional who uses their skills and knowledge in hacking to identify vulnerabilities and weaknesses in computer systems, networks, or applications. White hat hackers have permission from the organization to conduct security testing, and they work within the boundaries of legal and ethical frameworks. Their primary goal is to help organizations improve their security by discovering and reporting these vulnerabilities. Ethical hackers use various tools, techniques, and methodologies to simulate real-world cyberattacks and assess the target system's security posture. They often collaborate with the organization's IT and security teams to remediate the identifi...
Read more

Radio Waves

Image
  Introduction of Radio Waves Radio waves are a type of electromagnetic radiation with wavelengths longer than infrared light. They have frequencies ranging from about 3 Hz to 300 GHz and are widely used in communication systems, including radio broadcasting, television signals, mobile phones, satellite transmissions, and Wi-Fi networks . Properties of Radio Waves: Long Wavelengths – They range from millimetres to hundreds of kilometres in length. Low Energy – Compared to other electromagnetic waves like X-rays or ultraviolet rays, radio waves have lower energy. Ability to Travel Long Distances – Radio waves can propagate over large distances, making them ideal for communication. Reflection, Refraction, and Diffraction – They can bounce off surfaces, bend around obstacles, and spread out after passing through narrow openings. Uses of Radio Waves: Communication: AM/FM radio, television, mobile phones, and walkie-tal...
Read more

Semantic Technology

Image
Semantic Technology Semantic technology uses formal semantics to help AI systems understand language and process information the way humans do. Thus, they are able to store, manage and retrieve information based on meaning and logical relationships. Various businesses are already using semantic technology and semantic graph databases such as Ontotext's GraphDB to manage their content, repurpose and reuse information, cut costs and gain new revenue streams. Semantic Technology uses formal semantics to give meaning to the disparate data that surrounds us. Together with  Linked Data  technology, it builds relationships between data in various formats and sources, from one string to another, helping create context. Interlinked in this way, these pieces of raw data form a giant web of data or a  knowledge graph , which connects a vast amount of descriptions of entities and concepts of general importance. Semantic Technology defines and links data on the Web (or within an enter...
Read more