The algorithm for memory management is too much, what extent? Basically, the data structure that can be found can appear in a wide variety of memory management algorithms, arrays, linkers, haveh tables, binary trees, etc. are all placed here. Research memory management is really a interesting thing, and it can also greatly improve your programming capabilities.
Memory management solution
At least 3 sets of memory allocation functions are defined in MUDOS:
1. Build-in System Malloc - Introduction Function Library, Malloc, Realloc, Calloc, Free;
2. Satoria's Malloc - This is a function library created for MUDOS, which is fast than the built-in function in most systems;
3. BSD (Berkeley Software Distributions) Malloc - With the Malloc source code released by FreeBSD, the speed should be the fastest, but it will waste a lot of memory space.
Define at least 2 sets of packaging (WRAP) libraries:
1. Wrappedmalloc - a simple memory allocation function, providing limited memory allocation statistics: memory allocation (alloc), memory release number (free), memory redistribution (Realloc);
2. DEBUGMALLOC - As its name suggests: the memory allocation function used in the debug period, its implementation is more complicated, not only provides security check, but also the statistical functionality is also more perfect, such as the memory allocation can be found. Which data type provides memory space.
When compiling MUDOS, select different memory management programs by selecting different macros:
/ * macro.h * /
/ *
Define for Malloc, Free, Realloc, And Calloc Deprond Upon What Malloc
Package and optional wrapper is buy. this technique is buy because
Overlaming System Malloc with Another Function Also Named Malloc Doesn't
Work ON MAHINES That Have Shared Libraries. It Will Also Let
US Keep Malloc Stats Even WHEN SYSTEM MALLOC IS Used.
Please Refer to Options.h for selecting malloc package and wrapper.
* /
#if (defined (Sysmalloc) Defined (Smalloc) Defined (BSDmalloc)> 1
! Only One Malloc Package Should Be Defined
#ENDIF
#i (defined (Wrappedmalloc) Defined (Debugmalloc)> 1
! Only One Wrapper (at MOST) SHOULD BE Defined
#ENDIF
#if Defined (Wrapped Malloc) &&! defined (in_malloc_wrapper)
# Define malloc (x) Wrappedmalloc (x)
# Define free (x) # Define Realloc (x, y) WrappedRealloc (x, y)
# Define Calloc (x, y) WrappedCalloc (x, y)
# Define DXalloc (x, t, d) xalloc (x)
# Define Dmalloc (x, t, d) malloc (x)
# Define DREALLOC (X, Y, T, D) Realloc (x, y)
# Define DCalloc (x, y, t, d) Calloc (x, y)
#ELSE
# If defined (debugmalloc) &&! Defined (in_malloc_wrapper)
# Define malloc (x) Debugmalloc (x, 0, (char *) 0)
# Define Dmalloc (x, t, d) debugmalloc (x, t, d)
# Define Dxalloc (x, t, d) debugmalloc (x, t, d)
# Define Free (x) Debugfree (x)
# Define Realloc (x, y) DebugRealloc (x, y, 0, (char *) 0)
# Define DREALLOC (X, Y, Tag, DESC) DebugRealloc (x, y, tag, desc)
# Define Calloc (x, y) DebugCalloc (x, y, 0, (char *) 0)
# Define DCalloc (X, Y, Tag, DESC) DEBUGCALLOC (X, Y, Tag, DESC)
# Else
# Include "malloc.h"
# Endif
#ENDIF
/ * malloc.h * /
/ *
* To use sysmalloc or malloc replacements
* /
#if Defined (SYSMALLOC) || /
(Defined (Smalloc) && Defined (SBRK_OK) || /
Defined (bsdmalloc)
#define malloc (x) malloc (x)
#define free (x) free (x)
#define realloc (x, y) Realloc (x, y)
#define Calloc (x, y) Calloc (x, y)
#ENDIF
/ * Smalloc - Choice Between Replacement Or Wrapper * /
#if Defined (Smalloc) &&! defined (Sysmalloc)
# Neydef sbrk_ok
# Define smalloc_malloc malloc
# Define Smalloc_Free Free Free Free
# Define Smalloc_realloc Realloc
# Define Smalloc_Calloc Calloc
# Else
# Define malloc (x) Smalloc_malloc (x)
# Define free (x) smalloc_free (x)
# Define Realloc (x, y) Smalloc_realloc (x, y)
# Define Calloc (x, y) Smalloc_calloc (x, y) # Endif
#ENDIF
/ * BSDMalloc - Always a replacement * /
#if defined (bsdmalloc) &&! defined (Sysmalloc)
# Define bsdmalloc_malloc malloc
# Define BSDmalloc_free Free FREE
# Define bsdmalloc_realloc Realloc
# Define bsdmalloc_calloc Calloc
#ENDIF
#define Dxalloc (X, Tag, DESC) Xalloc (X)
#define Dmalloc (X, Tag, DESC) Malloc (x)
#define DREALLOC (X, Y, TAG, DESC) Realloc (x, y)
#define DCalloc (X, Y, Tag, DESC) Calloc (x, y)
In addition, there are some zero dispersion macros in other files, all macro definitions combine to make Mudos finally compile a suitable memory allocation scheme. The content of these two files (mAcro.h, malloc.h) is generally described in which memory allocation functions will be used to select different macros.
(Note: The connection between these macro definitions is intricate, and it is clear that there is two days to figure out which functions will be used to choose a macro. However, in C , you can completely leave these macro definitions, directly with template Control the library used by the customer code, such as allocator in STL, do not lose the efficiency, the visible template is really a good thing, no wonder Java, C # To add these features.)
Lisect several strange macro definitions that appear in the MUDOS source code:
1.
#if (defined (Sysmalloc) Defined (Smalloc) Defined (BSDmalloc)> 1
#Error Only One Malloc Package Should Be Defined
#ENDIF
Three macros define at least one, otherwise an error is reported. #Error is my own addition, the source code is "!", why is the source code not to #error?
In the #IF statement, you can use the size comparison symbol: ">", "<", "==", such as the following line code:
#if defined (aa) || Defined (bb) || defined (cc)
You can rewrote:
#if (defined (aa) defined (bb) defined (cc))> 0
2.
#if defined (bsdmalloc) &&! defined (Sysmalloc)
# Define bsdmalloc_malloc malloc
# Define BSDmalloc_free Free FREE
# Define bsdmalloc_realloc Realloc
# Define bsdmalloc_calloc Calloc
#ENDIF
If BSDMalloc is defined, Sysmalloc is not defined, then use Malloc to replace BSDmalloc_malloc. This is a very strange definition: If there is a definition of the malloc function during the compilation process, the alternative to the appearance here will cause the program to compile the error. For example, this example:
Void func () {
}
#define func funcvoid func () {//! error: function 'void __cdecl func (void)' Already Has A Body
}
Perhaps the author does not want to use BSDmalloc_malloc, "Always a Replacement" written in the comment, just replace the BSDmalloc_malloc in the existing code to build Malloc. The same problem also appears on Smalloc. It is not necessary to study it here, honestly say that these macros of these 龇 龇 易 让 让......
BSD Malloc
Although the new version of MudOS may not intend to use BSD malloc, but still need to introduce inside the algorithms involved - "Studying memory usage trends of programs is a very interesting activity" (Andrei Alexandrescu, Modern C Design: Generic Programming and Design Patterns ).
All of the storage assignments need to define an Overhead for each available memory block, record some allocation information to release memory. This is defined in the BSD Malloc library:
Union overhead {
Union overhead * ov_next; / * when free * /
Struct {
U_CHAR OVU_MAGIC; / * MAGIC NUMBER * /
U_CHAR OVU_INDEX; / * BUCKET # * /
#ifdef rcheck
u_short ovu_rmagic; / * Range Magic Number * /
U_INT OVU_SIZE; / * ACTUAL Block Size * /
#ENDIF
} OVU;
#define ov_magic ovu.ovu_magic
#define ov_index ovu.ovu_index
#define ov_rmagic ovu.ovu_rmagic
#define ov_size ovu.ovu_size
}
When the memory block is not used, these memory blocks form a linked list, and OV_Next points to the next memory. When the memory block is used, the OVU_Index identifies which of the memory partners is a list of linked lists. When it is released, the memory block is directly connected to that list.
BSD Malloc's memory block is managed by a linked list. The number of buckets is 30, and the memory size can be processed by 2 ^ (i 3). Each bucket is managed an unused memory link, and the linked list element includes an Overhead and a fixed size memory block. The allocation of the memory is always selected to make the target size of the bucket that is closest to not more than 2 ^ (i 3), such as the need to assign 15-byte size memory, plus Overhead size 4, total 19byte, will be used to use the element size 2 ^ (2 3) barrels, that is, the second (starting from 0). The bucket is defined as follows:
#define nbuckets 30
Static Union Overhead * Nextf [nbuckets];
The memory allocation and release of BSD Malloc is very simple.
distribution:
Find suitable barrel I.
If this bucket is used for the first time, the underlying function SBRK is called to allocate memory, and the memory is divided according to 2 (i 3) size, link each memory block into a chain table.
Assign NextF [i] to customer code, Nextf [i] points to Nextf [i] .OV_Next release:
Waplely release the memory block CP
OP = (union overhead *) ((CADDR_T) CP - SIZEOF (UNION overhead));
Remove the OP-> OV_Index value as a bucket index i
To release the memory block pointing to Nextf [i] .OV_NEXT
Nextf [i] pointing to the memory to release the memory block
From the implementation of BSD Malloc, it is not involved in the merged memory block due to the implementation of the BSD Malloc. However, since the size of the closest but not more than 2 ^ (i 3) is always selected, the waste is very considerable. For example, you need to assign 15 bytes, but the manager has paid 32bytete. This may be the reason why MUDOS finally gave up this function library?
Satoria's Malloc
This function library uses AVL Tree to manage memory. Because the subsequent chapter introduces the AVL Tree, it will not introduce it to its implementation (mainly the code too much - more than 1500 lines, sweat)
Wrappedmalloc
This packaging is simple and practical, and it is determined whether to cause memory leakage by checking stats.alloc_calls - stats.free_calls.
/ * wrappedmalloc.c * /
Typedef struct stats_s {
Unsigned int all_calls, alloc_calls, realloc_calls;
} Stats_t;
Static stats_t stats;
Void wrappedmalloc_init ()
{
Stats.free_calls = 0;
Stats.alloc_calls = 0;
Stats.realloc_calls = 0;
}
Inline void * WrappedRealloc P2 (Void *, PTR, INT, SIZE)
{
Stats.Realloc_calls ;
Return (Void *) Realloc (PTR, SIZE);
}
Inline void * Wrappedmalloc P1 (int, size)
{
Stats.alloc_calls ;
Return (void *) malloc (size);
}
Inline void * WrappedCalloc P2 (int, NItems, int, size)
{
Stats.alloc_calls ;
Return (void *) Calloc (Nitems, size);
}
Inline void WrappedFree P1 (Void *, PTR)
{
Stats.free_calls ;
Free (PTR);
}
Void Dump_malloc_data p1 (Outbuffer_t *, OB)
{
Outbuf_add (OB, "Using Wrapped Malloc: / N / N");
Outbuf_addv (OB, "#alloc calls:% 10lu / n", stats.alloc_calls);
Outbuf_addv (OB, "#free caverts:% 10lu / n", stats.free_calls;
Outbuf_addv (OB, "#alloc - #free:% 10lu / N",
Stats.alloc_calls - stats.free_calls;
Outbuf_addv (OB, "#Realloc Calls:% 10lu / N", Stats.Realloc_Calls);
}
Debugmalloc
This packaging is very complicated. Because it is used when it is Debug, it is of course a strong code without considering efficiency.
Just just by reading the code of the Debugmalloc function, you can see the Hope.
/ * Debugmalloc.c * /
#ifdef noisy_malloc
#define noisy (x) Printf (x)
#define noisy1 (x, y) Printf (x, y)
#define noisy2 (x, y, z) Printf (x, y, z)
#define noisy3 (w, x, y, z) Printf (w, x, y, z)
#ELSE
#define noisy (x)
#define noisy1 (x, y)
#define noisy2 (x, y, z)
#define noisy3 (w, x, y, z)
#ENDIF
#define md_overhead (sizeof (md_node_t))
Inline void * Debugmalloc P3 (int, size, int, tag, char *, desc)
{
Void * TMP;
IF (SIZE <= 0)
FATAL ("Illegal size in debugmalloc ()"); // Mudos end
Stats.alloc_calls ;
TMP = (void *) Malloc (Size MD_Overhead);
Mdmalloc (TMP, SIZE, TAG, DESC);
NOISY3 ("Malloc:% I (% x),% S / N", Size, (MD_Node_t *) TMP 1, DESC);
Return (md_node_t *) TMP 1;
}
Each time the memory is allocated, in addition to such a simple statistical function, each assignment is assigned to record some additional information, this structure is as follows:
Typedef struct md_node_s {
Int size; // memory size
Struct MD_NODE_S * NEXT; / / The next piece is allocated memory
#ifdef debugmalloc_extensions
INT ID; // This time allocated ID
INT tag; // data type
Char * desc; // Description
#ENDIF
#ifdef check_memory
Int magic;
#ENDIF
} MD_NODE_T;
Meet the memory after allocation is shown below:
Malloc is the actual allocation function, while MDmalloc processes the related operations of additional information nodes.
/ * Md.c * /
Void
Mdmalloc P4 (MD_Node_T *, Node, Int, Size, Int, Tag, Char *, DESC)
{
Unsigned int h;
Static int count = 0;
IF (! size) {
Debug_message ("MD: Debugmalloc: Attempted to Allocate ZERO BYTES / N");
#ifdef mdebug
Abort ();
#ENDIF
Return;
}
Total_malloced = size;
IF (Total_malloced> Hiwater {
Hiwater = TOTAL_MALLOCED;
}
H = (unsigned int) node% tablesize;
Node-> size = size;
Node-> Next = Table [H];
#ifdef check_memory
LEFT_MAGIC (NODE) = MD_MAGIC;
STORE_RIGHT_MAGIC (NODE);
#ENDIF
#ifdef debugmalloc_extensions
IF ((Tag & 0xFF) Totals [Tag & 0xFF] = size; Blocks [Tag & 0xFF] ; } IF ((tag >> 8) & 0xff) Totals [(TAG >> 8) & 0xFF] = size; Blocks [(Tag >> 8) & 0xFF] ; } Node-> tag = tag; Node-> id = count ; Node-> desc = desc? desc: "default"; IF (malloc_mask == node-> tag) { Debug_message ("MDMalloc:% 5D, [% -25S],% 8x: (% D) / N", Node-> tag, node-> desc, (unsigned int) PTR (Node), Node-> size); } #ENDIF Table [h] = node; } In the mdmalloc function, each additional information node is managed by a hash chain list, defined as follows: Static md_node_t ** table; Initialization is as follows: Void mdinit () { Int J; Table = (md_node_t **) Calloc (Tablesize, SIZEOF (MD_NODE_T *)); For (j = 0; j Totals [J] = 0; } } Therefore, the display list of the actual management of the additional information node is shown in the figure: Reference: [1] John Lion, "Leon's Unix Source Analysis" [2] Andrei Alexandrescu, Modern C Design: Generic Programming and Design Patterns [3] http://www.cs.colorado.edu/~ Zorn/malloc.html#bsd [4] http://gee.cs.oswego.edu/dl/html/malloc.html [5] http://magazine.nsfocus.net/index.php?act=magazine&do=view&mid=847
