SHARE
TWEET

MIPS Memory Manager

RetroZelda Mar 24th, 2016 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Mips Memory Manager - A Small program in mips to handle allocating and dealocating memory
  2. # Copyright (C) 2012  Erick "RetroZelda" Folckemer
  3.  
  4. # This program is free software: you can redistribute it and/or modify
  5. # it under the terms of the GNU General Public License as published by
  6. # the Free Software Foundation, either version 3 of the License, or
  7. # at your option) any later version.
  8. #
  9. # This program is distributed in the hope that it will be useful,
  10. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12. # GNU General Public License for more details.
  13. #
  14. # You should have received a copy of the GNU General Public License
  15. # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16.  
  17. .data
  18. ##### Block header Layout #####
  19. #  0) 4 bytes - size of block
  20. #  4) 4 bytes - address of prev block header; 0 if none
  21. #  8) 1 byte  - 0 if free, non-zero if not free
  22. #  9) 3 bytes - padding for word alignment
  23. # 12) open data start offset
  24. #  header size - 12 bytes
  25. #
  26. #
  27.  
  28.  
  29. Memory_Size_Total:  .word 0x8000 # 32kb
  30. Memory_Header_Size: .word 12 # 12 bytes
  31. Memory:         .word 0x10040000 # heap starting address
  32.  
  33. print_block_size:   .asciiz "block size: "
  34. print_block_prev:   .asciiz "\nblock prev: "
  35. print_block_addr:   .asciiz "\nblock address: "
  36. print_new_line:     .asciiz "\n"
  37. print_no_memory:    .asciiz "***** Out of Memory *****\n"
  38. print_leaked_memory:    .asciiz " Warning: Memory has been leaked!\n"
  39.  
  40. .text
  41. main:
  42.  
  43. jal init # init the memory blocks
  44. lw $a0, Memory # move our Memory address to display
  45. addi $a0, $a0, 12 # move to start of data block
  46. jal debug_print_block # display memory stats
  47. li $s1, 0 # start loop count
  48. allocate_loop:
  49. li $a0, 2048 # 2kb of data requested
  50. jal malloc # allocate the 2kb
  51. beqz $v0, no_memory_leave_loop # if malloc fails then leave this loop
  52. subi $sp, $sp, 4 # get room on stack
  53. sw $v0, 0($sp) # save address of allocated block onto stack
  54. move $a0, $v0 # move our allocated memory to a0 to print
  55. jal debug_print_block # print the info of this memory block
  56. addi $s1, $s1, 1 #increase loop count
  57. j allocate_loop
  58. no_memory_leave_loop:
  59. li $v0, 4 # print string syscall
  60. la $a0, print_no_memory
  61. syscall
  62. deallocate_loop:
  63. lw $a0, 0($sp) # get last address off stack
  64. addi $sp, $sp, 4 # move stack up
  65. jal free # free the memory
  66. subi $s1, $s1, 1 # decrease counter
  67. bnez $s1, deallocate_loop # keep going until counter is 0
  68. lw $t0, Memory_Size_Total # load total size
  69. lw $t1, Memory_Header_Size # load header size
  70. sub $t0, $t0, $t1 # remove header size from total size
  71. lw $t1, Memory # load start address
  72. lw $t1, 0($t1) # load remaining memory size
  73. beq $t1, $t0, exit_main # if remaining size != total size(minus the header) then we have a leak/problem
  74. li $v0, 4 # print string
  75. la $a0, print_leaked_memory
  76. syscall
  77. exit_main:
  78. lw $a0, Memory # move our Memory address to display
  79. addi $a0, $a0, 12 # move to start of data block
  80. jal debug_print_block # display memory stats
  81. li $v0, 10
  82. syscall
  83.  
  84. ########## sub routines ############
  85. ####################################
  86.  
  87. ##########################################
  88. ### init - initializes the memory pool ###
  89. init:
  90. li $t0, 0
  91. lw $t1, Memory # load the address of our memory
  92. lw $t2, Memory_Size_Total # load in the address of the total size
  93. lw $t3, Memory_Header_Size # load the header size
  94. sb $t0, 8($t1)  # mark memory as free
  95. sw $t0, 4($t1) # there isnt a prev block
  96. sub $t2, $t2, $t3 # update the space of the entire block remaining
  97. sw $t2, 0($t1) # set the bytes remaining for the block
  98. jr $ra
  99. ################ init end ################
  100. ##########################################
  101.  
  102. ###############################
  103. ### malloc - allocates data ###
  104. # in:
  105. ## a0 length of allocation
  106. # out:
  107. ## v0 - address of memory region
  108. ### - 0 if unavailable
  109. malloc:
  110. lw $t0, Memory # load the address of our memory
  111. lw $t1, Memory_Size_Total # load in the address of the total size
  112. lw $t3, Memory_Header_Size # load the header size
  113. lw $t4, Memory # the starting header to start
  114. add $t5, $t0, $t1 # the address of the end of the memory pool
  115. find_open_block:
  116. lb $t7, 8($t4) # load the free-byte
  117. bnez $t7, goto_next_block # keep looping if block isnt free
  118. lb $t7, 0($t4) # load the block size
  119. bge $a0, $t7, claim_open_block # stop looping; we can safely claim the block if enough space is available
  120. goto_next_block:
  121. addi $t6, $t4, 0 # save the prev block
  122. lw $t7, 0($t4) # save the block size
  123. add $t4, $t4, $t7 # increase by the block size
  124. add $t4, $t4, $t3 # increase by the header size(positived)
  125. bge $t4, $t5, no_open_blocks # we have passed the edge of the available pool
  126. j find_open_block # keep the block check going
  127. claim_open_block:
  128. lw $t8, 0($t4) # cache the block size
  129. bgt $a0, $t8, no_open_blocks # we will pass edge of available pool
  130. sw $a0, 0($t4) # save the block size
  131. sw $t6, 4($t4) # save the prev addr in header
  132. la  $t6, 0xffffffff # create a non-zero word to get a byte from
  133. sb $t6, 8($t4) # make free-byte be taken
  134. add $v0, $t4, $t3 # get the address of data-safe memory to return
  135. add $t6, $v0, $a0 # get address after our memory block
  136. sub $t8, $t8, $a0 # get the size of remaining space in old block
  137. sub $t8, $t8, $t3 # dont forget to remove header size from remaining size
  138. beqz $t8 return_from_malloc # if the block claim was snug, we can just leave
  139. sw $t8, 0($t6) # save new block size
  140. sw $v0, 4($t6) # save the new block as the prev block
  141. sb $zero, 8($t6) # this block is free
  142. j return_from_malloc # we can leave :)
  143. no_open_blocks:
  144. li $v0, 0 # load 0 to mark the function failed
  145. return_from_malloc:
  146. jr $ra # return from malloc
  147. ########## malloc end ##########
  148. ################################
  149.  
  150. ##################################
  151. ### free - free allocated data ###
  152. # in:
  153. ## a0 address of allocated block
  154. ## NOTE: Should clean up registers being used and where/how they are used to make clearer/cleaner
  155. free:
  156. sb $zero, -4($a0) # mark memory as free
  157. lw $t0, -8($a0) # load the prev block
  158. lw $t2, Memory_Header_Size # load the header size
  159. merge_right:
  160. lw $t1, -12($a0) # load the block size
  161. add $t1, $t1, $a0 # get the address to the next block
  162. lw $t3, Memory # load memory start address
  163. lw $t4, Memory_Size_Total # load total memory size
  164. add $t3, $t3, $t4 # get the address of the end of available memory
  165. bge $t1, $t3, merge_left # leave if next block is out of bounds
  166. lw $t3, 8($t1) # load the free byte in the next block
  167. bnez $t3, merge_left # leave if next block isnt free
  168. lw $t3, 0($t1) # load in the next block size
  169. lw $t4, -12($a0) # load in current block size
  170. add $t3, $t3, $t4 # combine the sizes
  171. add $t3, $t3, $t2 # include the header size
  172. sw $t3, -12($a0) # save the combined size
  173. merge_left:
  174. beqz $t0, return_from_free # if zero then we cant merge left
  175. lb $t1, 8($t0) # load the free byte
  176. bnez $t1, return_from_free # if not free, we cant merge left
  177. lw $t1, 0($t0) # load in the prev block size
  178. lw $t4, -12($a0) # load in current block size
  179. add $t1, $t1, $t4 # combine the sizes
  180. add $t1, $t1, $t2 # include the header size
  181. sw $t1, -12($a0) # save the combines size
  182.  
  183. return_from_free:
  184. jr $ra # return from malloc
  185. ########### free end ###########
  186. ################################
  187.  
  188. ###################################################
  189. ### debug_print_block - prints block to console ###
  190. # in:
  191. ## a0 - address of memory block
  192. debug_print_block:
  193. move $t0, $a0 # save the address
  194. li $v0, 4 # print string syscall
  195. la $a0, print_block_size
  196. syscall
  197. li $v0, 1 # print int syscall
  198. lw $a0, -12($t0) # value is block size
  199. syscall
  200. li $v0, 4 # print string syscall
  201. la $a0, print_block_prev
  202. syscall
  203. li $v0, 1 # print int syscall
  204. lw $a0, -8($t0) # value is block prev
  205. syscall
  206. li $v0, 4 # print string syscall
  207. la $a0, print_block_addr
  208. syscall
  209. li $v0, 1 # print int syscall
  210. la $a0, ($t0) # value is block prev
  211. syscall
  212. li $v0, 4 # print string syscall
  213. la $a0, print_new_line
  214. syscall
  215. jr $ra # return from debug_print_block
  216. ############## debug_print_block end ##############
RAW Paste Data
Top