内存学习——堆(heap)

目录

    • 一、概念
    • 二、自定义malloc函数
    • 三、Debug运行
    • 四、heap_4简单分析
      • 4.1 heap管理链表结构体
      • 4.2 堆初始化
      • 4.3 malloc使用
      • 4.4 free使用

一、概念

内存分为堆和栈两部分:

栈(Stack)是一种后进先出(LIFO)的数据结构,用于存储函数的调用栈、内存的分配操作、表达式求值的临时变量以及与程序中的控制流相关的数据。每当程序执行函数调用、变量声明或其他类型的操作时,都会在栈中添加一个栈帧(Stack Frame),用于存储函数的执行环境。

栈内存:主要存放函数地址、函数参数、局部变量等,空间较小,远小于堆内存,所以常有栈溢出错误。它由系统自动申请和回收,只由单线程使用,访问速度快,是连续内存,集中在内存块附近。

堆(Heap)则是用于分配程序中动态数据结构的内存空间,它的生命周期不由程序的函数调用栈管理,因此堆空间通常会被程序员直接管理。堆内存通常是一个可以被看做是一棵树的数组对象,它满足堆的性质:堆中某个节点的值总是不大于或不小于其父节点的值。堆空间为程序提供了极为灵活的空间分配和管理手段,既可以手动管理,也可以交由垃圾回收机制自动管理。

堆内存:主要存放new出来的对象和malloc申请的空间,空间大。它由程序分配,使用new或malloc申请,使用free或delete释放。堆内存中的实体数据地址都存储在栈变量中(即引用),以便能够高速访问。

总的来说,堆和栈在程序中都扮演着重要的角色。栈是一种高效的内存结构,用于存放基础数据类型和引用类型的变量,大大简化内存的管理,提高了程序的执行效率。堆空间则为程序提供了极为灵活的空间分配和管理手段。

被管理的内存称为堆,未被管理的内存称为栈:

  • 堆, heap,就是一块空闲的内存,需要提供管理函数
    • malloc:从堆里划出一块空间给程序使用
    • free:用完后,再把它标记为"空闲"的,可以再次使用
  • 栈, stack,函数调用时局部变量保存在栈中,当前程序的环境也是保存在栈中
    • 可以从堆中分配一块空间用作栈

在这里插入图片描述

二、自定义malloc函数

代码:

char heap_buf[1024]; //自定义1024字节内存的数组,模拟堆
int pos = 0; //指向堆数组可用空间的首地址

void *my_malloc(int size) //自定义malloc函数
{
	int old_pos = pos; //记录开辟空间的首地址
	pos += size; //malloc的空间大小
	return &heap_buf[old_pos]; //返回开辟空间的首地址
}

void my_free(void *buf) //可用自定义malloc函数,但是无法自定义free函数,后面分析原因
{
	/* err */
}


int main(void)
{
	char ch = 65; // char ch = 'A';
	int i;
	char *buf = my_malloc(100); //使用自定义的malloc函数在自定义堆数组中开辟100字节空间
		
	for (i = 0; i < 26; i++)
		buf[i] = 'A' + i; //在新开辟的空间中依次填入ABC……XYZ
	
	return 0;
}

三、Debug运行

1、查看heap_buf的首地址

在这里插入图片描述

2、查看malloc的buf首地址与heap_buf的首地址相同

在这里插入图片描述

3、多运行几次,ABCDE字母填入buf空间里,在heap_buf中也可以看到ABCDE

在这里插入图片描述

四、heap_4简单分析

4.1 heap管理链表结构体

对堆的管理意味着需要有一个链表结构体对空闲的堆空间和已使用的堆空间进行管理。

参考Heap_4的堆管理链表结构体:

typedef unsigned long size_t;

/* Define the linked list structure.  This is used to link free blocks in order
 * of their memory address. */
typedef struct A_BLOCK_LINK
{
    struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */
    size_t xBlockSize;                     /*<< The size of the free block. */
} BlockLink_t;

链表结构体包含2部分:

  • 下一个空闲块
  • 当前块的size

4.2 堆初始化

当第一次使用malloc时,会对Heap进行初始化:

static void prvHeapInit( void ) /* PRIVILEGED_FUNCTION */
{
    BlockLink_t * pxFirstFreeBlock;
    uint8_t * pucAlignedHeap;
    portPOINTER_SIZE_TYPE uxAddress;
    size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;

    /* 确保堆从正确对齐的边界开始。 */
    uxAddress = ( portPOINTER_SIZE_TYPE ) ucHeap;

    if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
    {
        uxAddress += ( portBYTE_ALIGNMENT - 1 );
        uxAddress &= ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK );
        xTotalHeapSize -= uxAddress - ( portPOINTER_SIZE_TYPE ) ucHeap;
    }

    pucAlignedHeap = ( uint8_t * ) uxAddress;

    /* xStart用于保存指向空闲块列表中第一项的指针。void强制转换用于防止编译器警告。 */
    xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
    xStart.xBlockSize = ( size_t ) 0;

    /* pxEnd用于标记空闲块列表的末尾,并插入到堆空间的末尾。 */
    uxAddress = ( ( portPOINTER_SIZE_TYPE ) pucAlignedHeap ) + xTotalHeapSize;
    uxAddress -= xHeapStructSize;
    uxAddress &= ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK );
    pxEnd = ( BlockLink_t * ) uxAddress;
    pxEnd->xBlockSize = 0;
    pxEnd->pxNextFreeBlock = NULL;

    /* 首先,有一个空闲块,它的大小是占用整个堆空间,减去pxEnd占用的空间。 */
    pxFirstFreeBlock = ( BlockLink_t * ) pucAlignedHeap;
    pxFirstFreeBlock->xBlockSize = ( size_t ) ( uxAddress - ( portPOINTER_SIZE_TYPE ) pxFirstFreeBlock );
    pxFirstFreeBlock->pxNextFreeBlock = pxEnd;

    /* 只有一个块存在——它覆盖了整个可用的堆空间。 */
    xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
    xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
}

通过代码可以看到,对Heap初始化时会创建一个xStart和*pxEnd :

//heap_4中定义:
/* 创建两个列表链接来标记列表的开始和结束。 */
PRIVILEGED_DATA static BlockLink_t xStart;
PRIVILEGED_DATA static BlockLink_t * pxEnd = NULL;
//heap_2中定义:
/* 创建两个列表链接来标记列表的开始和结束。 */
PRIVILEGED_DATA static BlockLink_t xStart, xEnd;

heap_2中的xStart, xEnd,用2个结构体代表头尾,不占用堆空间;

heap_4中是xStart, *pxEnd = NULL,pxEnd与heap_2中xEnd不一样,pxEnd占用了堆空间。这样做能够适配heap_5,heap_5支持多块不连续的内存合并,使用pxEnd链表,可以直接将pxEnd指向下一个非连续堆。

4.3 malloc使用

假设malloc开辟了3块空间,第一块空间从heap头开始100字节,第二块空间接着第一块空间100字节,第三块空间接着第二块50字节,最后释放了第二块,则示意图如下:

在这里插入图片描述

对照代码分析:

void * pvPortMalloc( size_t xWantedSize )
{
    BlockLink_t * pxBlock;
    BlockLink_t * pxPreviousBlock;
    BlockLink_t * pxNewBlockLink;
    void * pvReturn = NULL;
    size_t xAdditionalRequiredSize;

    vTaskSuspendAll();
    {
        /* 如果这是第一次调用malloc,那么堆将需要初始化来设置空闲块列表。 */
        if( pxEnd == NULL )
        {
            prvHeapInit();
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }

        if( xWantedSize > 0 )
        {
            /* 所需的大小必须增加,这样除了请求的字节数之外,它还可以包含BlockLink_t结构。为了对齐,可能还需要一些额外的增量。 */
            xAdditionalRequiredSize = xHeapStructSize + portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK );

            if( heapADD_WILL_OVERFLOW( xWantedSize, xAdditionalRequiredSize ) == 0 )
            {
                xWantedSize += xAdditionalRequiredSize;
            }
            else
            {
                xWantedSize = 0;
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }

        /* 检查我们尝试分配的块大小是否太大,以至于设置了顶部位。BlockLink_t结构的块大小成员的顶部位用于确定谁拥有该块-应用程序或内核,因此它必须是空闲的。 */
        if( heapBLOCK_SIZE_IS_VALID( xWantedSize ) != 0 )
        {
            if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
            {
                /* 从起始(最低地址)块开始遍历列表,直到找到一个足够大的块。 */
                pxPreviousBlock = &xStart;
                pxBlock = xStart.pxNextFreeBlock;

                while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
                {
                    pxPreviousBlock = pxBlock;
                    pxBlock = pxBlock->pxNextFreeBlock;
                }

                /* 如果到达终点标记,则没有找到足够大小的块。 */
                if( pxBlock != pxEnd )
                {
                    /* 返回指向的内存空间-在开始时跳过BlockLink_t结构。 */
                    pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );

                    /* 该块正在返回使用,因此必须从空闲块列表中删除。 */
                    pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

                    /* 如果块大于要求,则可以将其分成两个。 */
                    if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
                    {
                        /* 这个块将被分成两部分。根据请求的字节数创建一个新的块。void强制转换用于防止编译器发出字节对齐警告。 */
                        pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
                        configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );

                        /* 计算从单个块分割出的两个块的大小。 */
                        pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
                        pxBlock->xBlockSize = xWantedSize;

                        /* 将新块插入空闲块列表中。 */
                        prvInsertBlockIntoFreeList( pxNewBlockLink );
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }

                    xFreeBytesRemaining -= pxBlock->xBlockSize;

                    if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
                    {
                        xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
                    }
                    else
                    {
                        mtCOVERAGE_TEST_MARKER();
                    }

                    /* 块正在被返回——它被应用程序分配和拥有,没有“下一个”块。 */
                    heapALLOCATE_BLOCK( pxBlock );
                    pxBlock->pxNextFreeBlock = NULL;
                    xNumberOfSuccessfulAllocations++;
                }
                else
                {
                    mtCOVERAGE_TEST_MARKER();
                }
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }

        traceMALLOC( pvReturn, xWantedSize );
    }
    ( void ) xTaskResumeAll();

    #if ( configUSE_MALLOC_FAILED_HOOK == 1 )
    {
        if( pvReturn == NULL )
        {
            vApplicationMallocFailedHook();
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }
    }
    #endif /* if ( configUSE_MALLOC_FAILED_HOOK == 1 ) */

    configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
    return pvReturn;
}

4.4 free使用

假设使用free释放内存时,输入的参数pv是Heap中实际使用地址的首地址,但是malloc的空间除了实际使用的部分外还有一个头部的链表结构体,因此需要将pv地址向前移动xHeapStructSize,把malloc开辟空间的头部链表结构体与实际使用部分一同释放并插入到空闲Heap中:

void vPortFree( void * pv )
{
    uint8_t * puc = ( uint8_t * ) pv;
    BlockLink_t * pxLink;

    if( pv != NULL )
    {
        /* 被释放的内存在其前面有一个BlockLink_t结构。 */
        puc -= xHeapStructSize;

        /* 这种类型转换是为了防止编译器发出警告。 */
        pxLink = ( void * ) puc;

        configASSERT( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 );
        configASSERT( pxLink->pxNextFreeBlock == NULL );

        if( heapBLOCK_IS_ALLOCATED( pxLink ) != 0 )
        {
            if( pxLink->pxNextFreeBlock == NULL )
            {
                /* 该块被返回到堆中——它不再被分配。 */
                heapFREE_BLOCK( pxLink );
                #if ( configHEAP_CLEAR_MEMORY_ON_FREE == 1 )
                {
                    ( void ) memset( puc + xHeapStructSize, 0, pxLink->xBlockSize - xHeapStructSize );
                }
                #endif

                vTaskSuspendAll();
                {
                    /* 将此块添加到空闲块列表中。 */
                    xFreeBytesRemaining += pxLink->xBlockSize;
                    traceFREE( pv, pxLink->xBlockSize );
                    prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
                    xNumberOfSuccessfulFrees++;
                }
                ( void ) xTaskResumeAll();
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            mtCOVERAGE_TEST_MARKER();
        }
    }
}

其中heap4中把相邻的空闲内存合并为一个更大的空闲内存是在prvInsertBlockIntoFreeList函数中实现的:

static void prvInsertBlockIntoFreeList( BlockLink_t * pxBlockToInsert ) /* PRIVILEGED_FUNCTION */
{
    BlockLink_t * pxIterator;
    uint8_t * puc;

    /* 遍历列表,直到发现一个空闲块的下一个空闲块指针地址比插入的块的地址高,即得到比插入块地址小的相邻空闲块。
    问题:假设释放heap中地址最高的一段时,所有的空闲块地址都比要插入的块的地址低,此时该如何执行?*/
    for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
    {
        /* 这里什么都不用做,只需要迭代到正确的位置。 */
    }

    /* 插入的块和比其地址低的相邻块是否构成连续的内存块? 体现相邻空闲空间插入思想*/
    puc = ( uint8_t * ) pxIterator;

    if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
    {
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
        pxBlockToInsert = pxIterator;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    /* 插入的块和比其地址高的相邻块是否构成一个连续的内存块? 体现相邻空闲空间插入思想*/
    puc = ( uint8_t * ) pxBlockToInsert;

    if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
    {
        if( pxIterator->pxNextFreeBlock != pxEnd )
        {
            /* 把两个块组成一个大的块。 */
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
        }
        else
        {
            pxBlockToInsert->pxNextFreeBlock = pxEnd;
        }
    }
    else
    {
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
    }

    /* 如果被插入的块和比其地址低的相邻块不连续,而和比其地址高的相邻块连续,因此和比其地址低的相邻块的pxNextFreeBlock指针应该由原本指向和比其地址高的相邻块变为指向被插入的块 */
    if( pxIterator != pxBlockToInsert )
    {
        pxIterator->pxNextFreeBlock = pxBlockToInsert;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
}

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

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

相关文章

class072 最长递增子序列问题与扩展【算法】

class072 最长递增子序列问题与扩展【算法】 code1 300. 最长递增子序列 // 最长递增子序列和最长不下降子序列 // 给定一个整数数组nums // 找到其中最长严格递增子序列长度、最长不下降子序列长度 // 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequen…

【Java 基础】29 序列化

文章目录 1.定义2.目的3.使用1&#xff09;序列化2&#xff09;反序列化 3.应用场景4.注意事项总结 1.定义 序列化&#xff08;Serialization&#xff09;是将对象的状态转换为字节流的过程&#xff0c;以便将其存储到文件、数据库或通过网络传输 说简单点&#xff0c;序列化就…

关于DNS服务器地址总是127.0.0.1且无法解析域名地址

问题 笔者尝试nslookup解释域名时&#xff0c;出现服务器变成本地环回口地址&#xff0c;导致无法解析域名 C:\Users\Zsy>nslookup www.baidu.com 服务器: UnKnown Address: 127.0.0.1*** UnKnown 找不到 www.baidu.com: Server failed排查思路 尝试关闭虚拟网卡&#…

SQL语句的执行顺序怎么理解?

SQL语句的执行顺序怎么理解&#xff1f; 我们常常会被SQL其书写顺序和执行顺序之间的差异所迷惑。理解这两者的区别&#xff0c;对于编写高效、可靠的SQL代码至关重要。今天&#xff0c;让我们用一些生动的例子和场景来深入探讨SQL的执行顺序。 一、书写顺序 VS 执行顺序 SQ…

JS生成用户登录图形验证码

生成用户登录图形验证码的过程可以通过几个步骤来实现&#xff0c;包括创建画布&#xff0c;生成随机验证码文本&#xff0c;将验证码文本绘制到画布上&#xff0c;以及添加一些噪点和线条来增加复杂性。 HTML 首先&#xff0c;在HTML文件中创建一个<canvas>元素和一个…

c#生成二维码二维码中间添加定制LoGo

&#x1f680;介绍 &#x1f340;QRCoder是一个开源的.NET库&#xff0c;用于生成QR码&#xff08;Quick Response Code&#xff09;。这个库是用C#编写的&#xff0c;并且可以在.NET框架的各种版本上使用&#xff0c;包括.NET Framework, .NET Core, Mono, Xamarin等。QRCode…

深入解析Linux内核网络-拥塞控制系列(二)

上篇文章&#xff1a;深入解析Linux内核网络-拥塞控制系列(一&#xff09;对Linux内核网络中网络拥塞框架的框架进行了分析。本次针对具体的Cubic拥塞控制算法进行简单分析。在进行代码的梳理前&#xff0c;同样还是先来看一下相关概念、原理&#xff1a; 在上一篇文章中也提到…

电脑出现这些现象,说明你的固态硬盘要坏了

与传统机械硬盘&#xff08;HDD&#xff09;相比&#xff0c;固态硬盘&#xff08;SSD&#xff09;速度更快、更稳定、功耗更低。但固态硬盘并不是完美无瑕的&#xff0c;由于颗粒写入机制&#xff0c;可能会在七到十年的预期寿命之前出现故障。所以用户最好为最终故障做好准备…

vue3 自己写一个月的日历

效果图 代码 <template><div class"monthPage"><div class"calendar" v-loading"loading"><!-- 星期 --><div class"weekBox"><div v-for"(item, index) in dayArr" :key"index&q…

认识计算机的设备管理

在计算机系统中&#xff0c;除了处理器和内存之外&#xff0c;其他的大部分硬设备称为外部设备。它包括输入/输出设备&#xff0c;辅存设备及终端设备等。这些设备种类繁多&#xff0c;特性各异&#xff0c;操作方式的差异很大&#xff0c;从而使操作系统的设备管理变得十分繁杂…

数据仓库工具Hive

1. 请解释Hive是什么&#xff0c;它的主要用途是什么&#xff1f; Hive是一个基于Hadoop的数据仓库工具&#xff0c;主要用于处理和分析大规模结构化数据。它可以将结构化的数据文件映射为一张数据库表&#xff0c;并提供类似SQL的查询功能&#xff0c;将SQL语句转换为MapRedu…

使用 iperf 和 iftop 测试网络带宽

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…

京东商品详情数据在数据分析行业中的重要性

京东商品详情数据在数据分析行业中具有重要作用。这些数据提供了丰富的信息&#xff0c;可以帮助企业了解市场趋势、消费者需求、产品表现以及运营策略等多个方面。 首先&#xff0c;京东商品详情数据可以为企业提供市场趋势分析的依据。通过观察商品的销售量、销售额、价格等…

Qt 6.5 类库实例大全:QObject

大家好&#xff0c;我是20YC小二&#xff01;福利时间&#xff1a;欢迎(wx)扫码关注&#xff0c;免费领取《C程序员入门必修第一课&#xff1a;C基础课程》在线视频教程&#xff0c;还有更多技术分享&#xff01;#下面进入今天内容# 1. QObject 介绍 QObject 是 Qt 库中最重要…

RocketMq集成SpringBoot(待完善)

环境 jdk1.8, springboot2.7.3 Maven依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.3</version><relativePath/> <!-- lookup parent from…

C++学习笔记:继承

继承 什么是继承?继承的写法基类和派生类的赋值转换继承中的作用域派生类的默认成员函数单继承,多继承,虚拟继承is-a 和 has-a 什么是继承? 继承是C语言面向对象的三大特性之一&#xff0c;是面向对象程序设计使代码可以复用的最重要的手段,基本都是在一个类的基础上为了增加…

一个简单的可视化的A星自动寻路

一个简单的应用场景&#xff0c;流程图连线 源码&#xff1a; addExample("A星路径查找", function () {return {template: <div><div ref"main"></div></div>,data() { return {}; },computed: {},methods: {},mounted() {var c…

2-3、运算符

语雀原文链接 文章目录 1、算术运算符2、关系运算符3、逻辑运算符4、赋值运算符5、移位运算符6、位运算符(二进制位进行运算)7、条件运算符:三目运算符8、运算符的优先级 1、算术运算符 &#xff1a;加法-&#xff1a;减法*&#xff1a;乘法/&#xff1a;除法取商%&#xff1…

logback日志框架使用

依赖引入 <dependency><groupId>ch.qos.logback</groupId><artifactId>logback-classic</artifactId><version>1.1.7</version> </dependency> 使用logback日志框架只需要引入以上即可&#xff0c;(我们平时使用较多的Slf4j…

Fall in love with English

Fall in love with English 爱上英语 Hiding behind the loose dusty curtain, a teenager packed up his overcoat into the suitcase. 躲藏在布满尘土的松软的窗帘后边&#xff0c;一个年轻人打包他的外套到行李箱中。 He planned to leave home at dusk though there was th…