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 Kops0 yes 98% 5694 0.013128 4341 yes 94% 5848 0.013082 4472 yes 98% 6648 0.012994 5123 yes 99% 5380 0.013417 4014 yes 66% 14400 0.013624 10575 yes 89% 4800 0.014118 3406 yes 85% 4800 0.013772 3497 yes 55% 12000 0.016546 7258 yes 51% 24000 0.015425 15569 yes 48% 14401 0.030041 479
10 yes 45% 14401 0.015555 926
Total 75% 112372 0.171701 654Perf index = 45 (util) + 40 (thru) = 85/100
相关文章:
CSAPP Malloc lab
CSAPP Malloc Lab 目标 实现一个简单的动态存储分配器。 评分标准 空间利用率应当减少internal 和 external fragmentation. memory utilization memory utilization payload / heap size fragmentation internal fragmentation external fragmentation throughput T 越接…...
(黑马出品_06)SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
(黑马出品_06)SpringCloudRabbitMQDockerRedis搜索分布式 微服务技术ES搜索和数据分析 今日目标1. 查询文档1.1.DSL查询分类1.2.全文检索查询1.2.1.使用场景1.2.2.基本语法1.2.3.示例 1.3.精准查询1.3.1.term查询1.3.2.ran…...
算法学习之动态规划DP——背包问题
一、01背包问题 (一)题目 有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。 第i件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值…...
LeetCode刷题日志-17.电话号码的字母组合
纯暴力解法,digits有多长,就循环多少次进行字母组合 class Solution {public List<String> letterCombinations(String digits) {List<String> reslut new ArrayList<>();if(digits.equals(""))return reslut;Map<Inte…...
选修-单片机作业第1/2次
第一次作业 第二次作业 1、51 系列单片机片内由哪几个部分组成?各个部件的最主要功能是什么? 51系列单片机的内部主要由以下几个部分组成,每个部件的主要功能如下: 1. **中央处理器(CPU)**:这是…...
微信小程序开发系列(十七)·事件传参·mark-自定义数据
目录 步骤一:按钮的创建 步骤二:按钮属性配置 步骤三:添加点击事件 步骤四:参数传递 步骤五:打印数据 步骤六:获取数据 步骤七:父进程验证 总结:data-*自定义数据和mark-自定…...
企业战略管理 找准定位 方向 使命 边界 要干什么事 要做多大的生意 资源配置投入
AI突破千行百业,也难打破护城河 作为每个企业或个人的立命生存之本,有的企业在某个领域长期努力筑起了高高的护城河。 战略是什么?用处,具体内容 企业战略是指企业为了实现长期目标,制定的总体规划和长远发展方向。…...
记录西门子:IO隔离SCL编程
在PLC变量中创建IO输入输出 在PLC类型中创建输入和输出,并将PLC变量的输入输出名称复制过来 创建一个FC块或者FB块 创建一个DB块 MAIN主程序中:...
微信小程序如何实现下拉刷新
1.首先在你需要实现下拉刷新页面的json文件中写入"enablePullDownRefresh": true。 2.在js文件的onPullDownRefresh() 事件中实现下拉刷新。 实现代码 onPullDownRefresh() {console.log(开始下拉刷新)wx.showNavigationBarLoading()//在标题栏中显示加载图标this.d…...
React-useEffect
1.概念 说明:用于在React组件中创建不是由事件引起而是由渲染本身引起的操作,比如发送 A列AX请求,更改DOM等。 2.案例 // useEffect用于组件不是由事件引起的而是由渲染本身引起的操作,如ajax,更改Dom等。 import { useEffect,…...
web蓝桥杯真题:展开你的扇子
代码: /*TODO:请补充 CSS 代码*/#box:hover #item7 {transform: rotate(10deg); } #box:hover #item6 {transform: rotate(-10deg); } #box:hover #item8 {transform: rotate(20deg); } #box:hover #item5 {transform: rotate(-20deg); } #box:hover #i…...
阿里P9大佬分享:如何让代码更加灵活
面试官: 你好,今天我们要讨论的是命令模式。首先,你能解释一下什么是命令模式吗? 求职者: 当然可以。命令模式是一种行为设计模式,它将一个请求封装成一个对象,从而让你使用不同的请求、队列或者日志请求来参数化其他…...
SpringBoot中加载配置文件的优先级
在Spring Boot中,加载配置文件的优先级按照以下顺序进行,后续的配置会覆盖之前的配置: 默认属性:这些属性在Spring Boot本身中定义,并且通常是不可变的。它们作为后备值。 应用程序属性:这些属性在应用程序…...
Mysql命令行客户端
命令行客户端 操作数据库操作数据表 操作数据库 mysql> create database mike charsetutf8; Query OK, 1 row affected (0.01 sec) mysql> show databases; -------------------- | Database | -------------------- | information_schema | | mike …...
开源的python 游戏开发库介绍
本文将为您详细讲解开源的 Python 游戏开发库,以及它们的特点、区别和应用场景。Python 社区提供了多种游戏开发库,这些库可以帮助您在 Python 应用程序中实现游戏逻辑、图形渲染、声音处理等功能。 1. Pygame 特点 - 基于 Python 的游戏开发库。…...
批量提取PDF指定区域内容到 Excel 以及根据PDF里面第一页的标题来批量重命名-附思路和代码实现
首先说明下,PDF需要是电子版本的,不能是图片或者无法选中的那种。 需求1:假如我有一批数量比较多的同样格式的PDF电子文档,需要把特定多个区域的数字或者文字提取出来 需求2:我有一批PDF文档,但是文件的名…...
PCM会重塑汽车OTA格局吗(1)
目录 1.汽车OTA概述 2.ST如何考虑OTA? 2.1 Stellar四大亮点 2.2 PCM技术视角下的OTA 3.小结 1.汽车OTA概述 随着智能网联汽车的飞速发展,汽车OTA也越来越盛行; 目前来讲OTA分为FOTA和SOTA(Software-over-the-air)两种,区别…...
Intel® Extension for PyTorch*详细安装教程
最近在研究Intel的pytorch的加速拓展Intel Extension for PyTorch*,但是发现官网的文档全是英文的,不太好找安装教程。所以特此分享Intel Extension for PyTorch*的详细安装教程。 文章目录 一、安装所需系统要求1.1 硬件需求1.2 软件需求 二、准备2.1 安装驱动程序…...
云上攻防-云产品篇堡垒机场景JumpServer绿盟SASTeleport麒麟齐治
知识点 1、云产品-堡垒机-产品介绍&攻击事件 2、云产品-堡垒机-安全漏洞&影响产品 章节点: 云场景攻防:公有云,私有云,混合云,虚拟化集群,云桌面等 云厂商攻防:阿里云,腾讯…...
【顶刊|修正】多区域综合能源系统热网建模及系统运行优化【复现+延伸】
目录 主要内容 部分代码 结果一览 下载链接 主要内容 该程序复现《多区域综合能源系统热网建模及系统运行优化》模型并进一步延伸,基于传热学的基本原理建立了区域热网能量传输通用模型,对热网热损方程线性化实现热网能量流建模࿰…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
