block Memory { // #include // #include // #include // // struct node { // int size; // struct node *next; // char mem[]; // }; // #define HDRSIZE sizeof( struct node ) block node { local { public size: uquad; public next: uquad; public mem: public HDRSIZE: } local } block node // #define MAXSPACE 0x1000 // #define LONGSIZE 8 abs { MAXSPACE = 0x1000; LONGSIZE = 8; } abs // void **bottomStack; // void **low, **high; // struct node *freeList = ( struct node * ) memory; // struct node *inUseList = NULL; // struct node *newInUseList = NULL; // char memory[ MAXSPACE ]; // data { bottomStack: uquad; low: uquad; high: uquad; freeList: uquad; inUseList: uquad; newInUseList: uquad; memory: byte[ MAXSPACE ]; } data // int roundUp( int size ) { // return ( size + LONGSIZE - 1 ) / LONGSIZE * LONGSIZE; // } // block roundUp uses proc { code { public enter: body: addq $a0, 7; sra $a0, 3; sll $a0, 3, $v0; return: ret; } code } block roundUp // void initialise( void **low1, void **high1, void **topStack ) { // low = low1; // high = high1; // bottomStack = topStack; // freeList = ( struct node * ) memory; // freeList->size = MAXSPACE - node.HDRSIZE; // freeList->next = NULL; // inUseList = NULL; // newInUseList = NULL; // } // public block initialise uses proc { abs { low1 = a0; high1 = a1; topStack = a2; } abs code { public enter: body: ldiq $t0, low; stq $low1, ($t0); ldiq $t0, high; stq $high1, ($t0); ldiq $t0, bottomStack; stq $topStack, ($t0); ldiq $t0, freeList; ldiq $t1, memory; stq $t1, ($t0); ldiq $t0, MAXSPACE-node.HDRSIZE; stq $t0, node.size($t1); stq $zero, node.next($t1); ldiq $t0, inUseList; stq $zero, ($t0); ldiq $t0, newInUseList; stq $zero, ($t0); return: ret; } code } block initialise // void insertNode( struct node **list, struct node *element ) { // struct node *currNode; // while ( TRUE ) { // struct node *currNode = *list; // if ( currNode == NULL || currNode > element ) { // element->next = currNode; // *list = element; // return; // } // list = &currNode->next; // } // } // block insertNode uses proc { abs { list = a0; element = a1; currNode = s0; } abs code { public enter: lda $sp, -sav1($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); body: { do: ldq $currNode, ($list); { if: beq $currNode, then; cmpule $currNode, $element, $t0; blbs $t0, end; then: stq $currNode, node.next($element); stq $element, ($list); br return; end: } continue: lda $list, node.next($currNode); br do; end: } return: ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav1($sp); ret; } code } block insertNode // void removeNode( struct node **list ) { // struct node *element = *list; // *list = element->next; // element->next = NULL; // } // block removeNode uses proc { abs { list = s0; element = s1; } abs const { format: asciiz "removeNode( %12x )\n"; } const code { public enter: lda $sp, -sav2($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); init: mov $a0, $list; body: // ldiq $a0, format; // ldq $a1, ($list); // bsr IO.printf.enter; ldq $element, ($list); ldq $t0, node.next($element); stq $t0, ($list); stq $zero, node.next($element); return: ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav2($sp); ret; } code }block removeNode // void clear( struct node *currNode ) { // int i; // char *cp = currNode->mem; // for ( i = 0; i < currNode->size; i++ ) // cp[ i ] = 0; // } // block clear uses proc { abs { currNode = a0; } abs code { public enter: body: lda $t0, node.mem($currNode); ldq $t1, node.size($currNode); { for: clr $t2; while: cmplt $t2, $t1, $t3; blbc $t3, end; do: addq $t0, $t2, $t3; stb $zero, ($t3); continue: addq $t2, 1; br while; end: } return: ret; } code } block clear // // #define SMALLBLOCK (LONGSIZE * 4) // #define SMALLBLOCK (LONGSIZE * 0) // // void *findMemory( int size ) { // struct node **list; // for ( list = &freeList; *list != NULL; list = &(*list)->next ) { // struct node *currNode = *list; // if ( size <= currNode->size ) { // if ( currNode->size - size > node.HDRSIZE + SMALLBLOCK ) { // struct node *newFree = ( struct node * ) ( currNode->mem + size ); // newFree->size = currNode->size - size - node.HDRSIZE; // newFree->next = currNode->next; // *list = newFree; // currNode->size = size; // } // else { // *list = currNode->next; // } // clear( currNode ); // insertNode( &inUseList, currNode ); // return currNode->mem; // } // } // return NULL; // } // block findMemory uses proc { abs { // SMALLBLOCK = LONGSIZE * 4; SMALLBLOCK = LONGSIZE * 0; size = s0; list = s1; currNode = s2; newFree = s3; } abs code { public enter: lda $sp, -sav4($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); stq $s3, sav3($sp); body: { for: ldiq $list, freeList; while: ldq $currNode, ($list); beq $currNode, end; do: { if: ldq $t0, node.size($currNode); cmple $size, $t0, $t1; blbc $t1, end; then: { if: subq $t0, $size; ldiq $t1, node.HDRSIZE + SMALLBLOCK; cmple $t0, $t1, $t2; blbs $t2, else; then: addq $currNode, node.mem, $t2; addq $t2, $size, $newFree; subq $t0, node.HDRSIZE; stq $t0, node.size($newFree); ldq $t6, node.next($currNode); stq $t6, node.next($newFree); stq $newFree, ($list); stq $size, node.size($currNode); br end; else: ldq $t0, node.next($currNode); stq $t0, ($list); end: } mov $currNode, $a0; bsr clear.enter; ldiq $a0, inUseList; mov $currNode, $a1; bsr insertNode.enter; lda $v0, node.mem($currNode); br return; end: } increment: lda $list, node.next($currNode); br while; end: } clr $v0; return: ldq $s3, sav3($sp); ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav4($sp); ret; } code } block findMemory // void scanMemory( void **startAddress, void **endAddress ) { // void **address; // for ( address = startAddress; address < endAddress; address++ ) { // if ( ( void * ) memory <= *address && *address < ( void * ) ( memory + MAXSPACE ) ) // mark( *address ); // } // } // block scanMemory uses proc { abs { address = s0; startAddress = s1; endAddress = s2; } abs code { public enter: lda $sp, -sav3($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); init: mov $a0, $startAddress; mov $a1, $endAddress; body: { for: mov $startAddress, $address; while: cmpult $address, $endAddress, $t0; blbc $t0, end; do: ldq $t0, ($address); ldiq $t1, memory; cmpult $t0, $t1, $t2; blbs $t2, continue; ldiq $t1, memory + MAXSPACE; cmpult $t0, $t1, $t2; blbc $t2, continue; mov $t0, $a0; bsr mark.enter; continue: addq $address, 8; br while; end: } return: ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav3($sp); ret; } code } block scanMemory // void mark( void *address ) { // struct node **list; // for ( list = &inUseList; *list != NULL; list = &(*list)->next ) { // struct node *currNode = *list; // char *startData = currNode->mem; // char *endData = startData + currNode->size; // if ( ( void * ) startData <= address && address < ( void * ) endData ) { // removeNode( list ); // insertNode( &newInUseList, currNode ); // scanMemory( ( void ** ) startData, ( void ** ) endData ); // return; // } // } // } // block mark uses proc { abs { address = s0; list = s1; startData = s2; endData = s3; currNode = s4; } abs const { format: asciiz "mark( %12x )\n"; } const code { public enter: lda $sp, -sav5($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); stq $s3, sav3($sp); stq $s4, sav4($sp); init: mov $a0, $address; body: // ldiq $a0, format; // mov $address, $a1; // bsr IO.printf.enter; { for: ldiq $list, inUseList; while: ldq $currNode, ($list); beq $currNode, end; do: lda $startData, node.mem($currNode); ldq $t0, node.size($currNode); addq $startData, $t0, $endData; cmpult $address, $startData, $t0; blbs $t0, continue; cmpult $address, $endData, $t0; blbc $t0, continue; mov $list, $a0; bsr removeNode.enter; ldiq $a0, newInUseList; mov $currNode, $a1; bsr insertNode.enter; mov $startData, $a0; mov $endData, $a1; bsr scanMemory.enter; br return; continue: lda $list, node.next($currNode); br while; end: } return: ldq $s4, sav4($sp); ldq $s3, sav3($sp); ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav5($sp); ret; } code } block mark // void discard( struct node **list ) { // while ( *list != NULL ) { // struct node *element = *list; // *list = element->next; // insertNode( &freeList, element ); // } // } // block discard uses proc { abs { list = s0; element = s1; } abs const { format: asciiz "discard( %12x )\n"; } const code { public enter: lda $sp, -sav2($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); init: mov $a0, $list; body: { while: ldq $element, ($list); beq $element, end; do: // ldiq $a0, format; // mov $element, $a1; // bsr IO.printf.enter; ldq $t0, node.next($element); stq $t0, ($list); ldiq $a0, freeList; mov $element, $a1; bsr insertNode.enter; br while; end: } return: ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav2($sp); ret; } code } block discard // void mergeNodes( struct node *list ) { // for ( ; list != NULL; list = list->next ) { // while ( TRUE ) { // int size = list->size; // struct node *endData = ( struct node * ) ( list->mem + size ); // struct node *next = list->next; // if ( next == NULL || next != endData ) // break; // list->size = size + node.HDRSIZE + next->size; // list->next = next->next; // } // } // } // block mergeNodes uses proc { abs { list = a0; endData = s0; size = s1; next = s2; } abs code { public enter: lda $sp, -sav3($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); body: { while: beq $list, end; do: { while: lda $t0, node.mem($list); ldq $size, node.size($list); addq $t0, $size, $endData; ldq $next, node.next($list); beq $next, end; cmpeq $endData, $next, $t0; blbc $t0, end; do: addq $size, node.HDRSIZE; ldq $t0, node.size($next); addq $size, $t0; stq $size, node.size($list); ldq $t0, node.next($next); stq $t0, node.next($list); continue: br while; end: } continue: ldq $list, node.next($list); br while; end: } return: ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav3($sp); ret; } code } block mergeNodes // void garbageCollect( void **low, void **high, void **topStack, void **bottomStack ) { // scanMemory( low, high ); // scanMemory( topStack, bottomStack ); // discard( &inUseList ); // inUseList = newInUseList; // newInUseList = NULL; // mergeNodes( freeList ); // } // block garbageCollect uses proc { abs { low = s0; high = s1; topStack = s2; bottomStack = s3; } abs code { public enter: lda $sp, -sav4($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); stq $s3, sav3($sp); init: mov $a0, $low; mov $a1, $high; mov $a2, $topStack; mov $a3, $bottomStack; body: // bsr dump.enter; mov $low, $a0; mov $high, $a1; bsr scanMemory.enter; mov $topStack, $a0; mov $bottomStack, $a1; bsr scanMemory.enter; ldiq $a0, inUseList; bsr discard.enter; ldiq $t0, inUseList; ldiq $t1, newInUseList; ldq $t2, ($t1); stq $t2, ($t0); stq $zero, ($t1); ldiq $a0, freeList; ldq $a0, ($a0); bsr mergeNodes.enter; return: ldq $s3, sav3($sp); ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav4($sp); ret; } code } block garbageCollect // void *allocateMemory( int size, void **topStack ) { // void *memory; // size = roundUp( size ); // memory = findMemory( size ); // if ( memory == NULL ) { // garbageCollect( low, high, topStack, bottomStack ); // memory = findMemory( size ); // } // return memory; // } // block allocateMemory uses proc { abs { size = s0; topStack = s1; } abs code { public enter: lda $sp, -sav2($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); init: mov $a0, $size; mov $a1, $topStack; body: mov $size, $a0; bsr roundUp.enter; mov $v0, $size; mov $size, $a0; bsr findMemory.enter; { if: bne $v0, return; then: ldiq $a0, low; ldq $a0, ($a0); ldiq $a1, high; ldq $a1, ($a1); mov $topStack, $a2; ldiq $a3, bottomStack; ldq $a3, ($a3); bsr garbageCollect.enter; mov $size, $a0; bsr findMemory.enter; end: } return: ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav2($sp); ret; } code } block allocateMemory // public void *allocate( int size ) { // return allocateMemory( size, topStack ); // } // public block allocate uses proc { code { public enter: lda $sp, -sav6($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); stq $s3, sav3($sp); stq $s4, sav4($sp); stq $s5, sav5($sp); body: mov $sp, $a1; bsr allocateMemory.enter; return: ldq $s5, sav5($sp); ldq $s4, sav4($sp); ldq $s3, sav3($sp); ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav6($sp); ret; } code } block allocate // void printNode( struct node *p ) { // char *mem = p->mem; // int i; // printf( "%012x %012x %04x:", p, p->next, p->size ); // for ( i = 0; i < p->size; i++ ) { // printf( " %02x", ( unsigned char ) mem[ i ] ); // } // printf( "\n" ); // } // block printNode uses proc { abs { p = s0; i = s1; size = s2; mem = s3; } abs const { format1: asciiz "%12x %12x %4x:"; format2: asciiz "%2x"; } const code { public enter: lda $sp, -sav4($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); stq $s1, sav1($sp); stq $s2, sav2($sp); stq $s3, sav3($sp); init: mov $a0, $p; body: ldiq $a0, format1; mov $p, $a1; ldq $a2, node.next($p); ldq $a3, node.size($p); bsr IO.printf.enter; { for: clr $i; ldq $size, node.size($p); lda $mem, node.mem($p); while: cmplt $i, $size, $t0; blbc $t0, end; do: ldiq $a0, format2; addq $mem, $i, $t0; ldbu $a1, ($t0); bsr IO.printf.enter; continue: addq $i, 1; br while; end: } bsr IO.newline.enter; return: ldq $s3, sav3($sp); ldq $s2, sav2($sp); ldq $s1, sav1($sp); ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav4($sp); ret; } code } block printNode // void dumpList( struct node *list ) { // struct node *list; // for ( ; list != NULL; list = list->next ) // printNode( list ); // } // block dumpList uses proc { abs { list = s0; } abs code { public enter: lda $sp, -sav1($sp); stq $ra, savRet($sp); stq $s0, sav0($sp); init: mov $a0, $list; body: { while: beq $list, end; do: mov $list, $a0; bsr printNode.enter; continue: ldq $list, node.next($list); br while; end: } return: ldq $s0, sav0($sp); ldq $ra, savRet($sp); lda $sp, +sav1($sp); ret; } code } block dumpList // void dump() { // dumpList( inUseList ); // } public block dump uses proc { code { public enter: lda $sp, -sav0($sp); stq $ra, savRet($sp); body: ldiq $a0, inUseList; ldq $a0, ($a0); bsr dumpList.enter; return: ldq $ra, savRet($sp); lda $sp, +sav0($sp); ret; } code } block dump } block Memory