ListMalloc/Malloc_ReadMe at master · TstevetsT/ListMalloc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
MALLOC(2)                       Linux Programmer's Manual                      MALLOC(2)

NAME

       l_malloc

SYNOPSIS

       void *l_malloc (unsigned int size);
       void *l_calloc(unsigned int nmemb, unsigned int size);
       void *l_realloc(void *ptr, unsigned int size);
       void l_free(void *ptr);

DESCRIPTION


       l_malloc()  allocates size of bytes and returns a pointer to the allocated
       memory.  The memory is not initialized or cleared.   The data structure
       used to allocate memory is shown below.

              Blocks
       ---------------------    <-- Memory Ptr of Header
       ||  Size + Status  ||    4 Bytes Lowest bit is used for flag
       ---------------------    <-- Memory Ptr Addr Returned
       ||  Free Space     ||    Space available to the calling process
       ---------------------

       Allocated block headers are 4 bytes in size. The minimum block
       allocation is 4 bytes. With no space for user data. This will keep
       free blocks aligned in the heap. If any blocks are 4 bytes in size
       it will automatically be added to the allocation.  The heap is
       initialized by adjusting the break by 4000 KB.  When bytes are requested
       a walk down the storage viewing the headers of each block will occur.
       The size of block is used to find start of subsequent blocks.
       If an exact size match is encountered, it will be used.  As each block
       is tested, a pointer to the smallest block that is big enough for data is
       maintained.  When the bottom of the heap is reached, if a block has been
       identified it is used.  If a big enough block was not found, the heap
       will be grown by the requested block size.

       Size (4 Bytes)
       Size of allocated blocks can be up to a default 100,000 bytes in size
       change HEAPMAX to a large size to modify the max intial size of the heap
       located in malloc.asm

       Status (LSB) - uses AND operation to determine whether a status flag is
       utilized or not.

       00000000 - indicates the block is free
       00000001 - indicates the block is allocated

       Growing the heap.
       When a request for memory comes in, l_malloc will walk the blocks of the
       trying to find a block that is free and the exact size.  If found headers
       are updated and pointer is returned to caller immediatly.  If a larger free
       block is encountered, l_malloc stows it's pointer in ebx and continues
       walking the stack.  If another block is found that is as big as requested
       size but smaller than pointer held in ebx then ebx pointer is replaced.  If
       bottom of heap has been reached and ebx still contains a null pointer a big
       enough block was not found and the heap must be grown.  The heap is expanded
       by the size of the requested block.

       When a block of memory is freed the entire heap will be checked for blocks
       to coalesce due to the absence of a previous pointer and next pointer within
       the header information for a given block.

       l_calloc() and l_realloc() are extensions of l_malloc(). When one of these
       companion functions are called l_malloc() will be invoked. l_calloc ()
       allocates a block of memory and then the resulting block of memory is filled
       with zeroes. l_realloc() allocates a new block of memory when the first
       argument is null of the requested size. If a pointer is passed to l_realloc()
       in the first argument it will allocate a block of memory of a the specified
       size in argument two and then copy the first argument pointer into the new
       allocated block of memory. If the new memory block you copy into is smaller
       than the previous pointer then part of the copy will not be successful.

       l_free() is used to free blocks of memory that have been allocated by
       l_malloc(). When l_free() frees a block of memory it will then merge the
       entire heap starting from the highest address (or the beginning of the heap).
       If l_free() finds that the entire heap is empty when the caller invokes
       l_free() it will free the entire heap back to the kernel.


 RETURN VALUE

       On success, l_malloc(), l_calloc(), l_realloc(), returns a pointer to a
       reserved block of memory in the heap.  On error or failure, NULL is returned.
       On success, l_free() release the memory pointed to by ptr. If the ptr
       is NULL no action is taken.

 NOTES

	The priority for l_malloc's heap implementation is to maximize available
	storage by minimizing overhead.  For this reason the header is limited to
	four bytes.  The disadvantage to this is the heap must be walked from top
	to freed location during l_free inorder to coelesce the prior block.

 TESTING
	l_malloc is throughly tested by the test_malloc_list.c program.  It first
	displays the inital break.  Then it has a loop that calls l_malloc twenty
	times requesting between 1 and 2000 bytes.  Program has also successfully
	been tested for block sizes up to 32 KBytes. The program displays the returned
	pointer, the requested block size, the previous block size (reflecting 4 byte
	overhead + upto 3 additional bytes for 4 byte allignment), and a running used
	heap total.  Due to the method of growing the heap utilized (adding requested
	size to the bottom of the current heap) when allocation is not contiguous
	negative values may occur.  Next, ten randomly selected blocks will be freed.
	Since blocks are randomly selected from previously allocated blocks, the same
	block may be selected more than one time demonstrating that freeing an already
	freed block will not cause any errors.  Then twenty more l_malloc calls are
	made for random sizes.  Comparison of freed blocks and new pointers
	demonstrates successful reallocation of previously freed blocks.

	l_calloc is demonstrated by allocating a user defined length of 4 Byte
	blocks.  The number of requested cells are shown in a bytes@pointer format.
	It is shown that cells are zeroized and contiguous.  Next, data is randomly
	initialized to show that cells can be successfully accessed.

	l_realloc is demonstrated by reallocating the list from l_calloc.  User
	defines the length of the new list.  l_realloc will demonstrate l_calloc
	data moved to new address and can be shorter, the same length, or longer
	(new cells initialized to zero) than previous l_calloc list.

	l_free success is demonstrated by showing initial break, break before
	freeing, and break after freeing.  Initial and after freeing break is
	identical.

	list operations are demonstrated to all be successfull.