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、云产品-堡垒机-安全漏洞&影响产品 章节点: 云场景攻防:公有云,私有云,混合云,虚拟化集群,云桌面等 云厂商攻防:阿里云,腾讯…...
【顶刊|修正】多区域综合能源系统热网建模及系统运行优化【复现+延伸】
目录 主要内容 部分代码 结果一览 下载链接 主要内容 该程序复现《多区域综合能源系统热网建模及系统运行优化》模型并进一步延伸,基于传热学的基本原理建立了区域热网能量传输通用模型,对热网热损方程线性化实现热网能量流建模࿰…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
