CSAPP Malloc lab

CSAPP Malloc Lab

目标

实现一个简单的动态存储分配器。

评分标准

在这里插入图片描述
空间利用率应当减少internal 和 external fragmentation.

memory utilization

在这里插入图片描述
memory utilization = payload / heap size

fragmentation

在这里插入图片描述

internal fragmentation

在这里插入图片描述

external fragmentation

在这里插入图片描述

throughput

在这里插入图片描述

T 越接近Tlibc 吞吐量越高,也就是1s 内可以执行的op数量越多越好。
在这里插入图片描述

dynamic memory allocator

在这里插入图片描述
dynamic memory allocator分配heap的空间。
在这里插入图片描述
dynamic memory allocator 通过free list记录heap的free block, 收到free 请求的时候,查询free list 找到满足free request的block。
在这里插入图片描述
implicit free list 有多重查找free block 的方式,包括first fit, best fit, 和 next fit 等。
在这里插入图片描述
explicit free list 有多种insertion policy, 例如LIFO, 和address-ordered 等。
在这里插入图片描述
在这里插入图片描述
所以使用seglist 和first-fit.

allocator 设计重点

在这里插入图片描述
explicit list 和 seglist 还需要考虑
在这里插入图片描述

项目文件

在这里插入图片描述
主要是mm.c文件

介绍项目文件

memlib.c

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
return (void *)-1 是一个 C 语言中的语句,它的含义是将一个指针类型的值设置为 -1,然后将其转换为 void 指针类型,并返回。这通常用于表示一个特殊的错误条件或者指示函数执行失败。

mm.c 宏定义和常量

在这里插入图片描述
在这里插入图片描述
sizeof函数的单位是byte。
ALIGN 找到最小的alignment的倍数。

mm.c 文件需要实现的函数

在这里插入图片描述
mm_init 初始化heap和free list
mm_malloc 返回指向已经分配的block的payload的指针
mm_free 释放指向block的指针,为了避免fragmentation, 还需要执行free block 的合并。

seglist 设计和实现

指针操作

在这里插入图片描述
size = payload + header + footer
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

free list 函数操作

在这里插入图片描述
bp就是succ的地址,对于seglist的root节点。

DSIZE * (size + DSIZE + DSIZE -1)/DSIZE)

等价于

(size + DSIZE +DSIZE -1) & ~(0xF) 

free block 最小是2 * DSIZE (16 bytes),
对于 (0,16), 直接返回 2 * DSIZE;
对于 size = 16n+ (0, 16), 返回16 * (n+1);

mm_init 初始化seglist

在这里插入图片描述
extend_heap , 通过mem_sbrk 修改,heap 范围,(mem_brk 等指针的位置), 更新epilogue和prologue 的信息。

在这里插入图片描述
修改block 的allocated flag, 然后调用imme_coalesce, 查看prev_bp 和 next_bp是否可以合并,更新seglist 的 free block 数据。

在这里插入图片描述
使用first_fit查看是否有符合size大小的free blk, 没有的话,先合并,合并之后size仍然小于asize, 调用extend_heap函数。同时,如果找到的free blk 大于asize, 查看是否大于最小free blk size(header + footer + prev + succ, 4 word, word == 4 bytes), 大于进行split, 将剩余的部分加入seglist。

在这里插入图片描述
合并blk 存在4 种情况:
在这里插入图片描述
allocated blk 的header 和footer 不再记录size和allocate flag , 提高了heap的内存使用效率。

在这里插入图片描述

64位设备运行32程序

sudo yum install glibc.i686 libstdc++.i686

malloc 使用

#include <stdio.h>
#include <stdlib.h>

int main() {
    // 使用 malloc 分配足够的空间来存储一个指针
    int* ptr = (int*)malloc(sizeof(int*)*2);

    if (ptr == NULL) {
        // 检查内存分配是否成功
        printf("内存分配失败\n");
        return 1; // 返回错误码
    }

    // 假设有一个地址需要存储
    int x = 222;
    // 将地址存储到分配的内存中
    *ptr = &x;

    // 打印存储的地址值
    printf("存储的地址值:%p\n", *ptr);

    int * p = *ptr;
    printf("val: %d \n", *p);

    printf("存储的地址值:%p\n", &x);

    *(ptr+1) = 333;
    printf("val: %d \n", *(ptr+1));

    // 释放分配的内存
    free(ptr);

    return 0; // 返回成功码
}

在这里插入图片描述

段错误

0x00000000 导致段错误

[root@edb3963640a6 malloclab-handout]# ./mdriver -V -f short1-bal.rep
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Measuring performance with gettimeofday().

Testing mm malloc
Reading tracefile: short1-bal.rep
Segmentation fault (core dumped)

执行指令出现段错误

Core was generated by `./mdriver -V -f short1-bal.rep'.
Program terminated with signal 11, Segmentation fault.
#0  0x0804b29b in delete_blk (bp=0xf69a6888 '\004' <repeats 200 times>...) at mm.c:309
309         PUT(GET_SUCCP(pred_bp), succ_bp);
Missing separate debuginfos, use: debuginfo-install glibc-2.17-326.el7_9.i686
(gdb) bt
#0  0x0804b29b in delete_blk (bp=0xf69a6888 '\004' <repeats 200 times>...) at mm.c:309
#1  0x0804b113 in imme_coalesce (bp=0xf69a6888) at mm.c:245
#2  0x0804b60d in mm_free (ptr=0xf69a6888) at mm.c:455
#3  0x08049d8c in eval_mm_valid (trace=0x824a050, tracenum=0, ranges=0xfffef17c) at mdriver.c:674
#4  0x08049039 in main (argc=4, argv=0xfffef294) at mdriver.c:296

在这里插入图片描述
prev_bp 指针和 bp指针指向同一个位置?
在这里插入图片描述
测试可以通过的case, 不存在prev_bp 和 bp地址一样的问题。

在这里插入图片描述
prev_bp (0xf69fa888) 到 bp(0xf69fb038) 是一个size 6064的block, 对于0x 00000000 使用get_alloc 得到0, 所以导致prev_bp 获取的指针地址不准确,导致段错误。

在这里插入图片描述

mm_malloc 问题

Testing mm malloc
Reading tracefile: ./traces/amptjp-bal.rep
Checking mm_malloc for correctness, ERROR [trace 0, line 203]: Payload (0xf69d6038:0xf69d6040) lies outside heap (0xf69bd008:0xf69d6037)

在这里插入图片描述
New value 应该是1320。
在这里插入图片描述
在这里插入图片描述
old value = 1424 时候得打断点。
return 是bp 还是bp_header, 使用bp_header会导致
在这里插入图片描述
在这里插入图片描述
举个例子,size = 13, 13+8 +7 = 28
00000000 00000000 00000000 00011100 && ~(0xF) = 00000000 00000000 00000000 00000001
而不是 00000000 00000000 00000000 00010000.

在这里插入图片描述
在这里插入图片描述

realloc-bal.rep 和 realloc2-bal.rep

Reading tracefile: realloc-bal.rep
Checking mm_malloc for correctness, ERROR [trace 9, line 7]: Payload (0xf69ed038:0xf69ed2b7) overlaps another payload (0xf69ed240:0xf69ed2bf)

Reading tracefile: realloc2-bal.rep
Checking mm_malloc for correctness, ERROR [trace 10, line 7]: mm_realloc did not preserve the data from old block
[root@edb3963640a6 malloclab-handout]# ./mdriver -f ./traces/realloc-bal.rep -V
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Measuring performance with gettimeofday().

Testing mm malloc
Reading tracefile: ./traces/realloc-bal.rep
Segmentation fault (core dumped)

在这里插入图片描述
imme_coalesce 会合并prev_bp 和bp, old_bp 一般是bp, 但是prev_bp 和bp 合并时会修改bp_header, 导致oldbp_size小于DSIZE, memcpy函数出现段错误。

[root@edb3963640a6 malloclab-handout]# ./mdriver -V                            
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Using default tracefiles in /home/csapp/Malloc_Lab/malloclab-handout/traces/
Measuring performance with gettimeofday().

Testing mm malloc
Reading tracefile: amptjp-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: cccp-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: cp-decl-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: expr-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: coalescing-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: random-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: random2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: binary-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: binary2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: realloc-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: realloc2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   98%    5694  0.013128   434
 1       yes   94%    5848  0.013082   447
 2       yes   98%    6648  0.012994   512
 3       yes   99%    5380  0.013417   401
 4       yes   66%   14400  0.013624  1057
 5       yes   89%    4800  0.014118   340
 6       yes   85%    4800  0.013772   349
 7       yes   55%   12000  0.016546   725
 8       yes   51%   24000  0.015425  1556
 9       yes   48%   14401  0.030041   479
10       yes   45%   14401  0.015555   926
Total          75%  112372  0.171701   654

Perf index = 45 (util) + 40 (thru) = 85/100

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/455339.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue中ref 根据多选框所选数量,动态地变换box的高度

查看本专栏目录 关于作者 还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#x…

如何调整yolo混淆矩阵的大小,使其更加美观

1、找到xxx/utils/metrics.py 2、找到这个函数 3、往下拉找到这里&#xff0c;自己对照改一下 import seaborn as snarray self.matrix / ((self.matrix.sum(0).reshape(1, -1) 1E-9) if normalize else 1) # normalize columnsarray[array < 0.005] np.nan # dont a…

分布式之Sentinel使用和源码分析

Sentinel使用和源码分析 1、服务雪崩效应 在分布式系统中,由于网络原因或自身的原因,服务一般无法保证 100% 可用。如果一个服务出现了问题&#xff0c;调用这个服务就会出现线程阻塞的情况&#xff0c;此时若有大量的请求涌入&#xff0c;就会出现多条线程阻塞等待&#xff…

Redirect相应重定向无法访问WEB-INF下的静态资源,可以跳到外部资源(比如www.baidu.com)

相应重定向无法访问WEB-INF目录下静态资源&#xff0c;WEB-INF目录下静态资源受保护。 访问外部资源 访问Servlet5.do&#xff0c;就跳到百度页面

【快速上手ProtoBuf】proto 3 语法详解

1 &#x1f351;字段规则&#x1f351; 消息的字段可以⽤下⾯⼏种规则来修饰&#xff1a; singular &#xff1a;消息中可以包含该字段零次或⼀次&#xff08;不超过⼀次&#xff09;。 proto3 语法中&#xff0c;字段默认使⽤该规则。repeated &#xff1a;消息中可以包含该…

二,几何相交---4,BO算法---(3)数据结构

数据结构分两块&#xff0c;一个是某一时间状态的局部相交线段。一个是事件队列&#xff0c;是某一时刻局部相交线段的集合。

【Java设计模式】十九、中介者模式

文章目录 1、中介者模式2、案例3、总结 1、中介者模式 如图&#xff1a; 同事类之间关联较多时&#xff0c;整体出现网状结构&#xff0c;耦合度极高。一个对象一变动&#xff0c;好多对象都得改。若变为右边的星形结构&#xff0c;则一个类的变动&#xff0c;只影响自身与中介…

Vulnhub - DevGuru

希望和各位大佬一起学习&#xff0c;如果文章内容有错请多多指正&#xff0c;谢谢&#xff01; 个人博客链接&#xff1a;CH4SER的个人BLOG – Welcome To Ch4sers Blog DevGuru 靶机下载地址&#xff1a;DevGuru: 1 ~ VulnHub 目录 0x01 信息收集 0x02 Web漏洞利用 - W…

Ansible管理主机的清单------------inventory

一、 Ansible组成 INVENTORY&#xff1a;Ansible管理主机的清单 /etc/ansible/hosts 需要管理的服务清单,(将你需要管理的主机 、地址 或者名字 写入此文件) MODULES&#xff1a;Ansible执行命令的功能模块&#xff0c;多数为内置核心模块&#xff0c;也可自定义 PLUGINS&…

掌握抽象基础之20个必备原则,看完你还不会,你打我

抽象基础之20个必备原则 1. 面向对象编程&#xff08;OOP&#xff09;中抽象原则背后的基本思想是什么&#xff1f;2.抽象和封装的区别&#xff1f;3.提供一个现实生活中说明抽象的例子4.在编程语言中如何实现抽象&#xff1f;5.定义抽象类6.提供一个抽象类的真实世界场景7.解释…

大数据赋能,能源企业的智慧转型之路

在数字洪流中&#xff0c;大数据已经成为推动产业升级的新引擎。特别是在能源行业&#xff0c;大数据的应用正引领着一场深刻的智慧转型。今天&#xff0c;我们就来探讨大数据如何在能源企业中发挥其独特的魅力&#xff0c;助力企业提效降本&#xff0c;实现绿色发展。 动态监控…

学生时期学习资源同步-1 第一学期结业考试题5

原创作者&#xff1a;田超凡&#xff08;程序员田宝宝&#xff09; 版权所有&#xff0c;引用请注明原作者&#xff0c;严禁复制转载

Java推荐算法——特征加权推荐算法(以申请学校为例)

加权推荐算法 文章目录 加权推荐算法1.推荐算法的简单介绍2.加权推荐算法详细介绍3.代码实现4.总结 1.推荐算法的简单介绍 众所周知&#xff0c;推荐算法有很多种&#xff0c;例如&#xff1a; 1.加权推荐&#xff1a;分为简单的特征加权&#xff0c;以及复杂的混合加权。主要…

软考高级:系统工程方法(霍尔三维结构、切克兰德方法等)概念和例题

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…

Python+Selenium 自动化 - 开发环境搭建

PythonSelenium 自动化 - 开发环境搭建 一、Python 下载与安装二、Geany 代码编辑工具下载与安装三、代码运行演示 一、Python 下载与安装 Python 官网&#xff1a;https://www.python.org/ 首先在官网下安装包。 建议选择稳定版本&#xff0c;我这里下载的是 3.12.2 版本。 …

C++Qt学习——添加资源文件

目录 1、创建好了文件之后&#xff0c;在左边空白处按下CtrlN&#xff0c;创建Qt 以及Qt Resource File 2、写入名称&#xff0c;点击下一步 3、可以发现已经创建好啦。 4、点击Add Prefix 5、写上前缀&#xff0c;最好加上斜杠 6、选择提前放好的图片或者icon 7、发…

2024最新修复版独立付费进群系统源码全开源

1、修复SQL表 2、修复支付文件 3、修复支付图标不显示 4、修复定位、分销逻辑、抽成逻辑 5、新增支持源支付、易支付的支付接口 6、修复官方微信、支付宝支付接口文件 本来早就可以完工的&#xff0c;被99ai群里的几个傻逼耽搁了&#xff0c;做好自己就行了&#xff0c;这…

Learn OpenGL 09 投光物+多光源

将光投射(Cast)到物体的光源叫做投光物(Light Caster)。 投光物主要分为点光源&#xff0c;聚光灯&#xff0c;平行光。 平行光 当一个光源处于很远的地方时&#xff0c;来自光源的每条光线就会近似于互相平行。不论物体和/或者观察者的位置&#xff0c;看起来好像所有的光都…

C++:vector类

vector的介绍及使用 1. vector 是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c; vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以动态改变的…

解锁App推广新姿势:Xinstall二维码信息获取秘籍

在移动互联网时代&#xff0c;App推广已成为各大企业和开发者必不可少的一项工作。而在推广过程中&#xff0c;二维码作为一种便捷的下载和安装方式&#xff0c;被广泛应用于各种场景。然而&#xff0c;如何有效获取并利用这些二维码信息&#xff0c;却成为了一个令人头疼的问题…