MIPS循环双向链表新增分类时内存对齐错误排查求助

问题描述 #

这是一项大学作业任务，要求用循环双向链表实现分类化对象列表管理，删除分类规则如下：

• 若选中分类的对象列表为空，仅删除该分类；若存在下一个分类则自动选中它，否则置空相关指针
• 若对象列表非空，先释放所有对象内存，再按上述规则删除分类

目前新增分类时出现内存对齐错误，以下是相关MIPS汇编代码：

.data
slist:      .word 0
cclist:     .word 0
wclist:     .word 0
schedv:     .space 32
menu:       .ascii "\nColecciones de objetos categorizados\n"
        .ascii "====================================\n"
        .ascii "1-Nueva categoria\n"
        .ascii "2-Siguiente categoria\n"
        .ascii "3-Categoria anterior\n"
        .ascii "4-Listar categorias\n"
        .ascii "5-Borrar categoria actual\n"
        .ascii "6-Anexar objeto a la categoria actual\n"
        .ascii "7-Listar objetos de la categoria\n"
        .ascii "8-Borrar objeto de la categoria\n"
        .ascii "0-Salir\n"
        .asciiz "Ingrese la opcion deseada: "
error:      .asciiz "\nError: "
return:     .asciiz "\n"
flecha:     .asciiz "> "
catName:    .asciiz "\nIngrese el nombre de una categoria: "
selCat:     .asciiz "\nSe ha seleccionado la categoria: "
idObj:      .asciiz "\nIngrese el ID del objeto a eliminar: "
objName:    .asciiz "\nIngrese el nombre de un objeto: "
success:    .asciiz "\nLa operación se realizo con exito\n"

        .text
main:       la $t0, schedv # initialization scheduler vector
        la $t1, newcategory
        sw $t1, 0($t0)
        la $t1, nextcategory
        sw $t1, 4($t0)
        la $t1, prevcategory
        sw $t1, 8($t0)
        la $t1, listcategories
        sw $t1, 12($t0)
        la $t1, delcategory
        sw $t1, 16($t0)
        la $t1, newobject
        sw $t1, 20($t0)
        la $t1, listobjects
        sw $t1, 24($t0)
#       la $t1, delobject
#       sw $t1, 28($t0)

mainloop:   li $v0, 4
        la $a0, menu
        syscall
        li $v0, 5
        syscall     # Pedir un entero
        move $t2, $v0
condiciones:    blt $t2, 0, error101
        bgt $t2, 8, error101
        beq $t2, 0, end
        beq $t2, 1, opc1        
        beq $t2, 2, opc2
        beq $t2, 3, opc3    
        beq $t2, 4, opc4
        beq $t2, 5, opc5
        beq $t2, 6, opc6
        beq $t2, 7, opc7
        beq $t2, 8, opc8
        j mainloop
        
opc1:       jal newcategory
        j mainloop
opc2:       jal nextcategory
        j mainloop
opc3:       jal prevcategory
        j mainloop
opc4:       jal listcategories
        j mainloop
opc5:       jal delcategory
        j mainloop
opc6:       jal newobject
        j mainloop
opc7:       jal listobjects
        j mainloop
opc8:       #jal delobjet
        #j mainloop            
#-----------------------------------------------------------------------#
#               ERRORES                 # 
#-----------------------------------------------------------------------#
        
printerror:     
        move $t0, $a0
        li $v0, 4
        la $a0, error
        syscall
        li $v0, 1
        la $a0, ($t0)
        syscall
        li $v0, 4
        la $a0, return
        syscall
        j mainloop
error101:   li $a0, 101
        jal printerror
error201:   li $a0, 201
        jal printerror
error202:   li $a0, 202
        jal printerror
error301:   li $a0, 301
        jal printerror
error401:   li $a0, 401
        jal printerror
error501:   li $a0, 501
        jal printerror
error601:   li $a0, 601
        jal printerror  
error602:   li $a0, 602
        jal printerror
error701:   li $a0, 701
        jal printerror      
        
#-----------------------------------------------------------------------#
#               CATEGORIAS              #
#-----------------------------------------------------------------------#

newcategory:    
        addiu $sp, $sp, -4
        sw $ra, 4($sp)
        la $a0, catName # input category name
        jal getblock 
        move $a2, $v0 # $a2 = *char to category name
        la $a0, cclist # $a0 = list
        li $a1, 0 # $a1 = NULL
        jal addnode
        lw $t0, wclist
        bnez $t0, newcategory_end
        sw $v0, wclist # update working list if was NULL        
newcategory_end:
        li $v0, 0 # return success
        lw $ra, 4($sp)
        addiu $sp, $sp, 4
        jr $ra  

nextcategory:   lw $t0, wclist
        beqz $t0, error201 # wclist == 0
        lw $t1, 12($t0)
        beq $t0, $t1, error202 # prevcategory == 0
        sw $t1, wclist # update wclist
        li $v0, 4
        la $a0, selCat
        syscall
        lw $t1, 8($t0)
        li $v0, 4
        la $a0, ($t0)
        syscall
        li $v0, 4
        la $a0, success
        syscall
        li $v0, 0
        jr $ra
        
prevcategory:   lw $t0, wclist
        beqz $t0, error201 
        lw $t0, ($t0)   # $t0 = prevcategory
        beqz $t0, error202 # prevcategory != 0
        sw $t0, wclist # update wclist
        li $v0, 4
        la $a0, selCat
        syscall
        lw $t0, 8($t0)
        li $v0, 4
        la $a0, ($t0)
        syscall
        li $v0, 4
        la $a0, success
        syscall
        li $v0, 0
        jr $ra
        
listcategories: lw $t0, cclist
        beqz $t0, error301 
        lw $t1, wclist # $t1 = selected category in progress
        li $t2, 0 # i = 0 
        lw $t4, cclist #(aux)
catLoop:    bne $t0, $t4, elseCat # cclist != cclist(aux)?
        addi $t2, $t2, 1 # if cclist is repeated: i++
elseCat:    beq $t2, 2, listcategories_end 
        bne $t1, $t0 noeq # skip if wclist != cclist
        li $v0, 4     # (for current category)
        la $a0, flecha
        syscall # ">" 
noeq:       lw $t3, 8($t0)  # category name
        li $v0, 4
        la $a0, ($t3)
        syscall # print the category
        lw $t0, 12($t0) # next category
        j catLoop
listcategories_end:
        li $v0, 4
        la $a0, success
        syscall
        li $v0, 0
        jr $ra

delcategory:    
        lw $t0, cclist
        beqz $t0, error401
        addiu $sp, $sp, -4
        sw $ra, 4($sp)
        lw $a0, wclist 
        la $a1, slist 
        jal delnode
delcategory_end:
        li $v0, 4
        la $a0, success
        syscall
        li $v0, 0
        lw $ra, 4($sp)
        addiu $sp, $sp, 4
        jr $ra
        
#-----------------------------------------------------------------------#
#               OBJETOS                 #
#-----------------------------------------------------------------------#
        
newobject:  
        lw $t0, cclist 
        beqz $t0, error501
        addiu $sp, $sp, -4
        sw $ra, 4($sp)
        la $a0, objName
        jal getblock
        move $a2, $v0
        lw $t0, wclist
        la $a0, 4($t0)
        li $a1, 0 
        jal addnode
        lw $t0, 0($v0)
        lw $t1, 4($t0)
        addi $t1, $t1, 1
        sw $t1, 4($v0)
newobject_end:  
        li $v0, 0 # return success
        lw $ra, 4($sp)
        addiu $sp, $sp, 4
        jr $ra  
listobjects:    
        lw $t0, wclist # $t0 = selected category in progress
        beqz $t0, error601 # If there are no lists, error code 601
        lw $t0, 4($t0) # $t0 = list of objects of the current category 
        li $t2, 0 # i = 0
        lw $t4, ($t0) # $t4 = first element of object list
objLoop:    bne $t0, $t4, objElse
        addi $t2, $t2, 1 # if cclist is repeated: i++
objElse:    beq $t2, 2, listobjects_end
        lw $t3, 8($t0)  # object name
        li $v0, 4
        la $a0, ($t3)
        syscall # print the object
        lw $t4, ($t0) # $t4 = first element of object list
        lw $t0, 12($t0) # next object
        j objLoop
listobjects_end:
        li $v0, 4
        la $a0, success
        syscall
        li $v0, 0
        jr $ra
        
#-----------------------------------------------------------------------#
#               NODOS                   #
#-----------------------------------------------------------------------#

        # a0: list address
        # a1: NULL if category, node address if object
        # v0: node address added
addnode:
        addi $sp, $sp, -8
        sw $ra, 8($sp)
        sw $a0, 4($sp)
        jal smalloc
        sw $a1, 4($v0) # set node content
        sw $a2, 8($v0)
        lw $a0, 4($sp)
        lw $t0, ($a0) # first node address
        beqz $t0, addnode_empty_list
addnode_to_end:
        lw $t1, ($t0) # last node address
        # update prev and next pointers of new node
        sw $t1, 0($v0)
        sw $t0, 12($v0)
        # update prev and first node to new node
        sw $v0, 12($t1)
        sw $v0, 0($t0)
        j addnode_exit
addnode_empty_list:
        sw $v0, ($a0)
        sw $v0, 0($v0)
        sw $v0, 12($v0)
addnode_exit:
        lw $ra, 8($sp)
        addi $sp, $sp, 8
        jr $ra
        
        # a0: node address to delete
        # a1: list address where node is deleted
delnode:
        addi $sp, $sp, -8
        sw $ra, 8($sp)
        sw $a0, 4($sp)
        lw $a0, 8($a0) # get block address
        jal sfree # free block
        lw $a0, 4($sp) # restore argument a0
        lw $t0, 12($a0) # get address to next node of a0 node
        beq $a0, $t0, delnode_point_self
        lw $t1, 0($a0) # get address to prev node
        sw $t1, 0($t0)
        sw $t0, 12($t1)
        lw $t1, 0($a1) # get address to first node again
        bne $a0, $t1, delnode_exit
        sw $t0, ($a1) # list point to next node
        j delnode_exit
delnode_point_self:
        sw $zero, ($a1) # only one node
delnode_exit:
        jal sfree
        lw $ra, 8($sp)
        addi $sp, $sp, 8
        jr $ra

            
        # a0: msg to ask
        # v0: block address allocated with string

getblock:   addi $sp, $sp, -4
        sw $ra, 4($sp)
        li $v0, 4
        syscall
        jal smalloc
        move $a0, $v0
        li $a1, 16
        li $v0, 8
        syscall
        move $v0, $a0
        lw $ra, 4($sp)
        addi $sp, $sp, 4
        jr $ra

#-----------------------------------------------------------------------#
#           GESTION DE MEMORIA              # 
#-----------------------------------------------------------------------#

smalloc:
        lw $t0, slist   
        beqz $t0, sbrk
        move $v0, $t0
        lw $t0, 12($t0)
        sw $t0, slist
        jr $ra  # return
sbrk:
        li $a0, 16 # node size fixed 4 words
        li $v0, 9
        syscall 
        jr $ra  # return
sfree:
        lw $t0, slist
        sw $t0, 12($a0)
        sw $a0, slist # $a0 node address in unused list
        jr $ra  # return
end:        

错误根源分析 #

1. 内存用途混淆：getblock函数调用smalloc分配内存存储字符串，但smalloc是用来分配循环链表节点的（16字节，含prev/next指针等字段）。字符串写入后会覆盖节点的指针字段，导致后续访问链表节点时出现非法内存操作，包括对齐错误。
2. 函数参数传递错误：delcategory调用delnode时，错误传入空闲链表slist的地址，而非分类链表cclist的地址，导致链表结构被破坏。
3. 打印逻辑地址错误：nextcategory和prevcategory中打印分类名字时，错误访问原节点地址而非新选中节点的名字字段，引发非法内存访问。

修复方案 #

1. 分离字符串与链表节点内存 #

修改getblock，直接调用sbrk分配字符串缓冲区，不再复用链表节点内存：

getblock:   
        addi $sp, $sp, -4
        sw $ra, 4($sp)
        li $v0, 4
        syscall
        # 直接分配16字节字符串缓冲区，不使用链表节点内存
        li $a0, 16
        li $v0, 9
        syscall
        move $a0,