TLSF算法概念,原理,内存碎片问题分析
TLSF算法介绍
TLSF(Two-Level Segregated Fit,两级分割适应算法)。
- 第一级(first level,简称fl):将内存大小按2的幂次方划分一个粗粒度的范围,如一个72字节的空闲内存的fl是6(72介于26与27之间)。
- 第二级(second level,简称sl):在第一级的基础上做线性化的细粒度划分,分为多少等份由可配置的SLI参数确定,在32bit的系统中,最优的SLI为4或者5。
若为4,则等分为24=16份,每一份分割叫做Segregated list(分割链表)。

如图中的[104,…,111],链表上挂着的是大小范围为104…111的free blocks,数字104,…,111代表的是内存的大小,而非内存地址,TLSF算法将内存分成不同大小的块。
这个分割链表管理了两个内存块,一个大小为109字节,一个大小为104字节。
TLSF算法根据需要的内存大小,根据前面的两级分割算法计算出fl和sl,采用good fit策略,分割链表中的free block都必须大于需要的内存大小。
如需要一个72字节的内存,假设SLI=2(简单起见 ,做4等分),则fl=6,sl=0,加入选择sl=0这个分割链表,由于67小于72,不满足分割列表中所有free block大于需要的内存条件,所以取sl=1,如果sl==1这个分割链表不为空,则返回这个链表中第一个free block给到应用程序。
TLSF代码分析
TLSF在tlsf_malloc中先调用block_locate_free获取free block,再调用block_prepare_used获取free block的内存地址返回给应用程序。
void* tlsf_malloc(tlsf_t tlsf, size_t size)
{control_t* control = tlsf_cast(control_t*, tlsf);const size_t adjust = adjust_request_size(size, ALIGN_SIZE);block_header_t* block = block_locate_free(control, adjust); //获取空闲内存块头return block_prepare_used(control, block, adjust);//获取free block的内存地址
}
在这个过程中,与good fit相关的是两个函数mapping_search和serach_suitable_block()。
/* This version rounds up to the next block size (for allocations) */
static void mapping_search(size_t size, int* fli, int* sli)
{if (size >= SMALL_BLOCK_SIZE){const size_t round = (1 << (tlsf_fls_sizet(size) - SL_INDEX_COUNT_LOG2)) - 1;size += round;}mapping_insert(size, fli, sli);
}static void mapping_insert(size_t size, int* fli, int* sli)
{int fl, sl;if (size < SMALL_BLOCK_SIZE){/* Store small blocks in first list. */fl = 0;sl = tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT);}else{fl = tlsf_fls_sizet(size);sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2);fl -= (FL_INDEX_SHIFT - 1);}*fli = fl;*sli = sl;
}
mapping_search先对size做一个四舍五入,再根据size计算fl和sl,作为下一步的search_suitable_block的起点。
static block_header_t* search_suitable_block(control_t* control, int* fli, int* sli)
{int fl = *fli;int sl = *sli;/*** First, search for a block in the list associated with the given** fl/sl index.*/unsigned int sl_map = control->sl_bitmap[fl] & (~0U << sl);if (!sl_map){//没有free_block存在,搜索下一个first levelconst unsigned int fl_map = control->fl_bitmap & (~0U << (fl + 1));if (!fl_map){//没有可用的free block,内存已经用完return 0;}fl = tlsf_ffs(fl_map);*fli = fl;sl_map = control->sl_bitmap[fl];}tlsf_assert(sl_map && "internal error - second level bitmap is null");sl = tlsf_ffs(sl_map);*sli = sl;//返回分割链表的第一个free blockreturn control->blocks[fl][sl];
}
相关文章:
TLSF算法概念,原理,内存碎片问题分析
TLSF算法介绍 TLSF(Two-Level Segregated Fit,两级分割适应算法)。 第一级(first level,简称fl):将内存大小按2的幂次方划分一个粗粒度的范围,如一个72字节的空闲内存的fl是6(72介…...
sharding-jdbc实现分库分表
shigen日更文章的博客写手,擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长,分享认知,留住感动。 😅😅最近几天的状态有点不对,所以有几天没有更新了。 当我们的数据量比较大…...
JDK中lock锁的机制,其底层是一种无锁的架构实现的,公平锁和非公平锁
简述JDK中lock锁的机制,其底层是一种无锁的架构实现的,是否知道其是如何实现的 synchronized与lock lock是一个接口,而synchronized是在JVM层面实现的。synchronized释放锁有两种方式: 获取锁的线程执行完同步代码,…...
c++通过serial库进行上下位机通信
编辑 风紊 现役大学牲,半退休robomaster视觉队员 写在前面 本文章主要介绍的是如何通过开源的serial库和虚拟串口实现上位机和下位机通信。 需求 假设下位机有这样一个数据报发送给上位机 struct DataRecv {char start s;TeamColor color TeamColor::Blu…...
【傻瓜级JS-DLL-WINCC-PLC交互】7.C#直连PLC并读取PLC数据
思路 JS-DLL-WINCC-PLC之间进行交互,思路,先用Visual Studio创建一个C#的DLL控件,然后这个控件里面嵌入浏览器组件,实现JS与DLL通信,然后DLL放入到WINCC里面的图形编辑器中,实现DLL与WINCC的通信。然后PLC与…...
指针常量和常量指针的区别
文章目录 指针常量常量指针即是指针常量又是常量指针 指针常量 指针常量的本质是常量,表示的是 这个指针所指向的地址不能发生改变。即指针变量的值(即地址值)不能发生修改。但是指针所指向的那块内存里的值是可以修改的。 注意:…...
离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。 两个问题需要考虑: 1. 原数组中可能有重复元素,需要去重。 2. 如何算出离散化后的值(离散化后保序,使用二分)。 题目链接: …...
【海思SS528 | VO】MPP媒体处理软件V5.0 | VO模块编程总结
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
逻辑卷管理器lvm
啥意思,个人理解就是可以将物理分区合并一起组成大的磁盘,也可以移除其中的某个分区。 有四个概念需要了解下 PV,物理卷,VG 卷用户组,PE物理扩展块,LV逻辑卷 p物理,v卷,g用户组&a…...
函数声明后的“ - >”是什么?
这种语法的优势之一是可以在函数的返回类型中使用函数参数,使得返回类型更灵活。 先来看一个使用尾返回类型的例子: #include <iostream> auto add(int a, int b) -> int {return a b; }int main() {std::cout << add(3, 4) <<…...
51爱心流水灯32灯炫酷代码
源代码摘自远眺883的文章,大佬是30个灯的,感兴趣的铁汁们可以去看看哦~(已取得原作者的许可):基于STC89C51单片机设计的心形流水灯软件代码部分_单片机流水灯代码_远眺883的博客-CSDN博客 由于博主是个小菜鸡ÿ…...
将不同时间点的登录状态记录转化为不同时间段的相同登录状态SQL求解
题目 有不同时间点的登录状态记录表state_log如下 请使用sql将其转化为如下表的不同时间段的相同登录状态记录 思路分析: 此类问题需要用到lag或lead函数取上下行对应的数据,然后对前后结果做比较打标签(0或1),再…...
正则表达式与SQL数据库教程
使用正则表达式通过用例查询 Postgres 数据库: 正则表达式(又名 Regex) 正则表达式是一个强大的工具,广泛用于模式匹配和文本操作。 几乎所有编程语言都支持它们,并且经常用于文本提取、搜索和匹配文本等用例。 正则…...
HTML_web扩展标签
1.表格标签 2.增强表头表现 4.表格属性(实际不常用) 结构标签: 合并单元格: 更多请查看主页...
论文阅读:Distributed Initialization for VVIRO with Position-Unknown UWB Network
前言 Distributed Initialization for Visual-Inertial-Ranging Odometry with Position-Unknown UWB Network这篇论文是发表在ICRA 2023上的一篇文章,本文提出了一种基于位置未知UWB网络的一致性视觉惯性紧耦合优化测距算法( DC-VIRO )的分布式初始化方法。 对于…...
scrapy爬虫中间件和下载中间件的使用
一、关于中间件 之前文章说过,scrapy有两种中间件:爬虫中间件和下载中间件,他们的作用时间和位置都不一样,具体区别如下: 爬虫中间件(Spider Middleware) 作用: 爬虫中间件主要负…...
手敲单链表,简单了解其运行逻辑
1. 链表 1.1 结构组成 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 链表的结构如下图所示,是由很多个节点相互通过引用来连接而成的;每一个节点由两部分组成,分别数据域&…...
Redis RDB
基于内存的 Redis, 数据都是存储在内存中的。 那么如果重启的话, 数据就会丢失。 为了解决这个问题, Redis 提供了 2 种数据持久化的方案: RDB 和 AOF。 RDB 是 Redis 默认的持久化方案。当满足一定条件的时候, 会把当前内存中的数据写入磁盘, 生成一个快照文件 dump.rdb。Redi…...
Elasticsearch一些函数查询
1. 根据价格分组统计数量,每组区间为2000, filter_pathaggregations 设置查询结果只展示函数结果 也有date_histogram函数根据日期分组等等 GET order/_search?filter_pathaggregations {"aggs": {"hist_price": {"histogr…...
竞赛选题 : 题目:基于深度学习的水果识别 设计 开题 技术
1 前言 Hi,大家好,这里是丹成学长,今天做一个 基于深度学习的水果识别demo 这是一个较为新颖的竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-senior/pos…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
