// Author Robinkin from Devonit .inc # ifndef Memory_C # Define Memory_c
// # Define test_memory # define iOS # define debug // # Define test_little / * This system has a set of stacks of specific sizes, analog stack storage management on this area * Provides two key functions Malloc (int) and Free (void *) * * * This version of the system, using a 256K size stack * divided into 256 copies, 1K size, * If the user applies more than 1K size space, the direct partner algorithm is large Buddy_table (big table) finds a suitable size idle block; * * If the user applies for less than 1K size space, * is on a 1K idle block, build a small buddy_table (small table) * a small table management 32 block , Size is 32-byte small pieces. * After a small table is assigned, create a new small table until the space of the big table is also full of * * spatial allocation, then apply for a space, report Memory Full Fair * * /
#define null 0 # ifdef iOS # include
#define malloc my_malloc # define free my_free
#define uchar unsigned char # Define ushort unsigned short
Void * malloc (int size); // Assign a space void free (void *); // Release a pointer #define null 0
Void free_little (void * addr); void free_big (void * addr);
#define false 0 # Define true 1
#define BIG_BLOCK_SIZE 1024 // chunk of each 1k # define BIG_BLOCK_MAX 256 // how many 1k chunks #define STACK_MAX BIG_BLOCK_SIZE * BIG_BLOCK_MAX // # define BLOCKID_MAX 2 * BIG_BLOCK_MAX // binary tree node
/ / The first node divided 1024 * 128 1024 * 128, the second, and 3 further segmentation //1 2 4... 2 18=2 ^ 19-1,
#define LITTLE_BLOCK_SIZE 32 // 32 bytes of a tile #define LITTLE_BLOCK_MAX BIG_BLOCK_SIZE / LITTLE_BLOCK_SIZE // 1024/32 # define LITTLE_BLOCKID_MAX 2 * LITTLE_BLOCK_MAXchar SYS_STACK [STACK_MAX]; // Storage Pool
Struct buddy_address_table {void * address [BIG_BLOCK_MAX]; // Start Address Ushort OCCU_ID [BIG_BLOCK_MAX]; // Hash position occupied, 0 means unwind, non-0, point to the ID
Bool semi [blockid_max]; // is partially occupied, use this array to represent a two-fork boof occupied [blockid_max]; // is fully occupied, use this array to represent a binary tree};
Buddy_address_table bd = {null};
Struct Little_buddy {void * address [little_block_max]; // start address uchar occu_id [Little_block_max]; // Hash position occupied, 0 indicates that it is not occupied, non-0 point points to the occupied IDBool SEMI [little_blockid_max]; // is part Occupation, use this array to represent a binary tree bous occupied [little_blockid_max]; // is completely occupied, use this array to represent a binary tree
INT IDX; // The small table itself is IDX in the big table (to release the small table) BOOL FULL;};
Void * Find_Little_Space (Little_Buddy * LB, INT I, INT Size, VOID * AddR); Void * Find_Space (INT I, INT Size, VOID * AddR); Void Error (INT X) {# ifdef debug # Endif};
INT BIG_SIZE (Int IDX) {
INT S = Stack_max; INT i; while (IDX! = 1) {s = S / 2; if (IDX% 2 == 0) {IDX = IDX / 2;} else {IDX = (IDX-1) / 2 ;}}} Return s;}
INT Little_size (int idx) {
INT S = BIG_BLOCK_SIZE; INT I; While (IDX! = 1) {s = S / 2; if (IDX% 2 == 0) {IDX = IDX / 2;} else {IDX = (IDX-1) / 2 ;}}} Return s;}
// Establish an release information stack, when it is released, it is not immediately released, but the advanced stack / / stack is full or space is full, release efficiency // little_buddy * lb_list [bigl_block_max] = {NULL }
// Most BIG_BLOCK_MAX a small table - a big buddy block can be a small budy table
INT GET_IDX_LITTLE (Little_Buddy * LB, Void * AddR) {INT i = (int) addr; int k = i% little_block_max; while (lb-> ipcu_id [k]) {k ; if (k == little_block_max) {k = 0;}} RETURN K; // Find the insertion position} int GET_IDX (VOID * ADDR) {INT i = (int) addr; int K = I% BIG_BLOCK_MAX; while (bd.occu_id [k]) {k ; IF (k == BIG_BLOCK_MAX) {k = 0;}} Return K; / / Find the insertion position of AddRE}
Void * malloc (int size) {void * addr; int idx; // find the idle block ID
#ifdef debug cout << "Target Space: << size << Endl; #ENDIF
IF (size <= BIG_BLOCK_SIZE) {// is smaller, assign int i = 0 with a small table; while (lb_list [i]! = null && lb_list [i] -> full! = 1) {
#ifdef debug cout << "Search Little" << Endl; #ENDIF // The unenfacked table IF (addr = find_little_space (lb_list [i], 1, size, lb_list [i])) {RETURN ADDR;} i ;} // existing small table can not find enough space, establish a new small table if (addr = find_space (1, big_block_size, sys_stack) {// Find space LB_LIST in the big table I] = (little_buddy *) addr; // The space occupied by the small table itself
// little Table Initialize Int J; For (j = 0; j
For (j = 0; j
} Lb_list [i] -> idx = idx;
/ / Remove the space of the small table itself Find_Little_Space (LB_LIST [I], 1, SIZEOF (Little_Buddy), AddR); // Find the appropriate small empty block IF (AddR = FIND_LITTLE_SPACE (LB_LIST [i) through the idle block space described by the small table ], 1, size, addr;} else {return null;}}} returnif;}}} Return Find_Space (1, size, sys_stack); // From the root node start to find free space
}
/ /// void * find_little_space (Little_Buddy * LB, INT I, INT SIZE, VOID * AddR) {
IF (little_block_size> size) {size = little_block_size;} int SZ = little_size (i);
IF (little_blockid_max
// Semi-available space IF (LB-> SEMI [I]) {
#ifdef detail cout << "SEMI" << i << "<< SZ <<" << size << Endl; #ENDIF IF (SZ <= 2 * size) {return null;} else {IF ! lb-> occupied [2 * i]) {void * ADR; if (ADR = FIND_LITTLE_SPACE (LB, 2 * I, Size, Addr)) {Return ADR;}} else {char * ad = (char *) AddR Return Find_Little_Space (LB, 2 * i 1, Size, Ad SZ / 2);}}}
// is a completely available space IF (SZ> = size) {// There is available space
#ifdef detail cout << "Space:" << i << "<< SZ <<" << size << Endl; #ndif if (SZ> = 2 * size) {// is too big, continue Small LB-> SEMI [I] == 1; // itself half occupies VOID * ADR; if (ADR = FIND_LITTLE_SPACE (LB, 2 * I, Size, Addr)) {Return ADR;} else {char * ad = (char *) addr; returnof_little_space (lb, 2 * i 1, size, ad sz / 2);};} // find the right available space
INT K = GET_IDX_LITTLE (LB, ADDR); LB-> Address [k] = addr; lb-> occu_id [k] = i; // note the ID small table LB-> Occupied [i] = true;
#ifdef debug cout << "Space:" << i << "<< SZ <<" << size << Endl; # #ndif rett initdr; // Return to the storage space first address} else {// The size of the block has exceeded the maximum limit of this small table, LB-> full = 1; Return Null;
}} ////
Void * Find_Space (int I, int size, void * addr) {// start looking for size from Index is a block of size
IF (BIG_BLOCK_SIZE> SIZE) {size = BIG_BLOCK_SIZE;} int SZ = BIG_SIZE (i);
#ifdef detail cout << i << "<< SZ <<" << size << Endl; #ndifif (blockid_max // semi-available space IF (bd.semi [i]) {if (SZ <= 2 * size) {return null;} else {if (! Bd.occupied [2 * i]) {void * ADR; IF ADR = Find_SPACE (2 * i, size, addr)) {Return ADR;}} else {char * ad = (char *) addr; returnof_space (2 * i 1, size, ad sz / 2);} } // is a completely available space IF (SZ> = size) {// There is a free space if (SZ> = 2 * size) {// is too big, continued to be divided into bd.SEMI [i] == 1; / / Itself half occupies Void * ADR; if (ADR = Find_SPACE (2 * i, size, addr)) {Return ADR;} else {char * ad = (char *) addr; returnof_space (2 * i 1, size , AD SZ / 2);}; / / Find the right available space INT k = get_idx (add); bd.address [k] = addr; bd.occu_id [k] = i; // note the ID small table bd.occupied [I] = true; #ifdef debug cout <
} #ifdef detail cout << "begin to assign" << i << Endl; #ndif if (! bd.occupied [i] && sz> size) {// There is a free space IF (SZ> 2 * size) {/ / Still too big, continue to be divided into bd.occupied [i] == true; // itself is not available #ifdef detail cout << "Virtual Assign" << i << "<< SZ << Endl << ENDL ; #ndif void * ADR; if (ADR = Find_Space (2 * i, size, addr)) {bd.occupied [2 * i] = 1; // Left node is not returned ADR;} else {char * ad = (char *) Addr; bd.occupied [2 * i 1] = 1; // Left node is not empty return find_space (2 * i 1, size, ad sz / 2);}; Else {// Find the right available space INT k = get_idx (addr); bd.address [k] = addr; bd.occu_id [k] = i; // note the ID small table of the corresponding address #ifdef Detail Cout << "OCCU_ID:" << k << "<< (int) addr << endl; #ENDIF #ifdef debug cout << "Best Suit:" << I << "<< SZ << Endl; #ndif rett bd.address [k]; // Return the first address and space size} else {# IFDEF DETAIL COUT << "Begin Search Sub_Node" << Endl; #ndif if (bd.occupied [i]) {// This block takes up void * ADR; if (ADR = Find_Space (2 * i, size, addr)) {// Looking for the left node Return ADR;} else {char * ad = (char *) addr; returnof_space (2 * i 1, size, ad sz / 2);}} Else {// The size of the block has exceeded the maximum error (98); # ifdef debug if (1 == i) {COUT << "Memory Full << Endl;} #ENDIF RETURN NULL;} }}} //// Void free_big_id (int K) {// Release the upper mating point IF (0 == k) {#ifdef debug1 cout << "root" << Endl; #ndif rett;} if (1 == k) {#ifdef debug cout << "root freed" << Endl; #ENDIF BD.OcCupied [1] = false; / / Clear index pointed to the space Bd.Semi [1] = false; // Clear the space Return pointed to the index;} IF (0 == k% 2) {// Left Node #ifdef Detail Cout << K << "Left Virutal Freed" << Endl; #ENDIF IF (! bd.occupied [k 1] ||! bd . Semi [K 1]) {// On the right side #ifdef detail cout << k 1 << "Right Blank TOO" << Endl; #ENDIF free_big_id (k / 2); bd.occupied [k] = false; / / Clear index pointer point to space BD.SEMI [ K] = false; // Empty the space pointed to by the index}} else {// is the right node #ifdef detail cout << k << "Right Virutal Freed" << Endl; #ENDIF IF (! bd.occupied [k-1] ||! bd.semi [k-1]) {// 左 也 #ifdef debug cout << k-1 << "Left blank TOO" << Endl; #ENDIF Free_BIG_ID ((k-1) / 2); bd.occupied [k] = false; / / Clear index pointer point to space BD.SEMI [K] = false; / / Clear index pointer points to space} }} // end //// int memory_size_little (void * addr) { INT TARGET = (int) addr; int d; for (int D = 0; D Little_buddy * p = lb_list [d]; while (p-> address [k]! = Addr ||! P-> occu_id [k]) {k ; if (k == BIG_BLOCK_MAX) {k = 0;}} Return Little_size (P-> OCCU_ID [K]);}} Return -1; INT MEMORY_SIZE_BIG (Void * Addr) { INT TARGET = (int) addr; INT Head = Target% BIG_BLOCK_MAX; int Tail = Head; #ifdef detailcout << Head << "<< (int) addr << Endl; #ENDIF IF (bd.address [head] == addr && bd.occu_id [head]! = 0) {; Else {head ; while (tail! = head && (bd.occu_id [head] == 0 || bd.address [head]! = addr) {#ifdef debug // cout << (int) bd.address [ HEAD] << "; # endifhead ; if (head == BIG_BLOCK_MAX) {head = 0;}}}} INT k = head; if (head == tail) {returnemory_size_little (addr);} Return Big_Size (bd.occu_id [k]); } // void free_big (void * addr) { INT TARGET = (int) addr; INT Head = Target% BIG_BLOCK_MAX; int Tail = Head; #ifdef detailcout << Head << "<< (int) addr << Endl; #ENDIF IF (bd.address [head] == addr && bd.occu_id [head]! = 0) {; Else {head ; while (tail! = head && (bd.occu_id [head] == 0 || bd.address [head]! = addr) {#ifdef debug // cout << (int) bd.address [ HEAD] << "; #ENDIF HEAD ; if (head == BIG_BLOCK_MAX) {head = 0;}}} INT k = head; if (head == tail) {free_little (add);} IF (1 == bd.occu_id [k]) {// is not rooted point #ifdef debug cout << "BIG ROOT FREED" << Endl; #ENDIF BD.OCCUPIED [1] = false; / / Clear index pointed to the space bd.semi [1] = false; / / Clear index pointed to the space BD.OCCU_ID [K] = 0; // Empty out of an index position Return;} IF (BD.OCCU_ID [K]% 2 == 0) {// Left Node #ifdef debug cout << bd.occu_id [k] << "Left real freed" << endl; #ndif if (! bd) Occupied [bd.occu_id [k] 1]) {// On the right side, empty free_big_id (bd.occu_id [k] / 2);} } else {// is the right node #ifdef debug cout << bd.occu_id [k] << "Right Real Freed" << Endl; #ENDIF IF (! bd.occupied [bd.ocu_id [k] -1]) {// left side empty free_big_id ((bd.occu_id [k] -1) / 2);}} BD.OCCUPIED [BD.OCCU_ID [K]] = false; / / Clear index pointed to the space BD.SEMI [BD.OCCU_ID [K]] = false; / / Clear index pointer to the space BD.OCCU_ID [K] = 0; // Empty out of an index position } // void free_little_id (Little_Buddy * P, INT K) {if (0 == k) {#ifdef debugcout << "root" << Endl; #endif return;} if (1 == k) {#ifdef debug Cout << "Little Root Freed" << Endl; #ENDIF P-> Occupied [1] = false; / / Clear index pointed to the space P-> SEMI [1] = false; / / Clear the space of the index pointed to;} IF (0 == k% 2) {// Left node #ifdef debug1 cout << k << "Left virutal freed" << Endl; #ENDIF if (! p-> occupied [k 1] ||! P-> SEMI [K 1]) {// On the right side #ifdef debug1 cout << k 1 << "Right Blank TOO" << Endl; #ndif free_little_id (p, k / 2); p-> occupied [k] = false; / / Clear index pointed to the space P -> SEMI [K] = false; / / Clearing the space pointed to by the index}} else {// is the right node #ifdef debug1 cout << k << "Right Virutal Freed" << Endl; #ENDIF IF (! p-> occupied [k-1] ||! P-> SEMI [K-1]) {// 也 #ifdef debug1 cout << k-1 << "Left blank TOO" << Endl; #ENDIF Free_Little_ID (p, (k-1) / 2); P-> Occupied [k] = false; / / Clear index pointed to space} }}} // end free_little_id //// Void free_little (void * addr) { INT TARGET = (int) addr; int d; for (int D = 0; D Little_buddy * p = lb_list [d]; while (p-> address [k]! = Addr ||! P-> OCCU_ID [K]) {k ; if (k == BIG_BLOCK_MAX) {k = 0;}} int ID = P-> OCCU_ID [K]; P-> occupied [id] = false; p-> semi [id] = false; #ifdef debug1 cout << "idx" << k << Endl << Endl; #ENDIF if (id == 1) {// is a small table root node free (P); // Release the bulk root #ifdef debug cout << "free little table << endl << Endl; #ENDIF} if (id% 2 == 0) {// left node IF (! p-> occupied [ID 1] &&! P-> SEMI [ID 1]) {// On the right side is also empty #ifdef debug cout << "Right Also Blank: << ID << Endl << Endl; #ndif free_little_id (p, id / 2); // Release the upper layer Return;}} Else {// Right Number IF (! P-> Occupied [P-> OCCU_ID [K] -1]) {// The left side is also empty #ifdef debug cout << "Left also blank: << P-> OCCU_ID [K] << Endl << Endl; #ndif free_little_id (p, (id-1) / 2); // Release the upper node return;} }}}} // // void free (void * addr) {int target = (int) addr; int base = (int) sys_stack; IF (target Else {// small table #ifdef debug cout << "free_little" << Endl; #ndif free_little (addr);} } INT MEMORY_SIZE (VOID * AddR) {// Chech That How Many Space Has Assign To Itint Target = (int) addr; int base = (int) sys_stack; IF (target Else {// small table #ifdef debug cout << "size_little" << Endl; #ndif retturn memory_size_little (addr);}} / * 99 Unknown error 98 Space insufficient 96 Releases the address (pointer) in a buddy system * * * / # ifdef test_memoryint main () {double * d [10]; #ifdef test_bigint * a = (int *) malloc (1000 * sizeof (int)); a [999] = 1; free (a); Double * d [10]; d [0] = (double *) malloc (2000 * sizeof (double)); d [1] = (double *) malloc (2000 * sizeof (double)); d [2] = (Double *) Malloc (4000 * SizeOf (Double)); D [3] = (Double *) malloc (8000 * sizeof (double)); int i; for (i = 0; i <4; i ) {free (d [i]); // d [0] = (double *) malloc (8000 * sizeof (double)); d [1] = (double *) malloc (16000 * sizeof (double)); // D [2] = (double * ) Malloc (4000 * sizeof (double)); // D [3] = (double *) Malloc (8000 * sizeof (double)); D [1] [15999] = 1; Free (D [1]); D [1] = (double *) Malloc (32000 * sizeof (double)); Free (d [1]); D [1] = (double *) malloc (42000 * sizeof (double)); # ENDIF #ifdef test_littled [0] = (double *) Malloc (2); d [1] = (double *) malloc (4); d [2] = (double *) malloc (8); D [3] = Double *) malloc (16); d [4] = (double *) malloc (32); d [5] = (double *) malloc (64); int i; for (i = 0; i <6; i ) {Free (d [i]);} # endif} #ENDIF / / ENDIF TEST_MEMORY # Endif // endif memory_c
