标签: heap

我试图找到免费商店通常被称为堆的官方(或足够好)的原因.

除了它从数据段的末尾增长之外,我无法想到一个很好的理由,特别是因为它与堆数据结构几乎没有关系.

注意:很多人都提到它只是一大堆没有组织的东西.但对我来说,术语堆物理意味着一堆物理依赖于彼此的东西.你从下面拉出一个,其他一切都在它上面坍塌,等等.换句话说,对我来说,堆松的声音组织起来很糟糕(例如,最新的东西在上面).这并不是一个堆在大多数计算机上实际工作的方式,但如果你把东西放在堆的开头然后增长它我想它可以工作.

可能重复:
何时最好使用堆栈而不是堆,反之亦然？

我已经阅读了关于堆与堆栈的其他一些问题,但它们似乎更关注堆/堆栈的作用而不是使用它们的原因.

在我看来,堆栈分配几乎总是首选,因为它更快(只需移动堆栈指针与在堆中查找可用空间),并且您在使用它时不必手动释放已分配的内存.我可以看到使用堆分配的唯一原因是,如果要在函数中创建对象,然后在函数作用域之外使用它,因为堆栈分配的内存在从函数返回后自动取消分配.

还有其他原因使用堆分配而不是我不知道的堆栈分配吗？

我想知道为什么堆概念作为算法(实现make_heap,pop_heap, push_heap,sort_heap),而不是一个容器.我特别感兴趣的是一些人的解决方案也可以解释为什么set和map容器而不是类似的算法集合(make_set add_set rm_set等).

每个线程都有自己的堆栈,但它们共享一个公共堆.

每个人都清楚堆栈是针对本地/方法变量和堆的,例如/类变量.

在线程之间共享堆有什么好处.

有几个线程同时运行,因此共享内存可能会导致并发修改,互斥等开销等问题.堆中的线程共享哪些内容.

为什么会这样？为什么不让每个线程拥有自己的堆呢？任何人都可以提供一个真实世界的例子,线程如何利用共享内存？

我一直在努力学习堆溢出攻击的基础知识.我最感兴趣的是使用损坏或修改块元数据作为攻击的基础,但我也对其他建议持开放态度.我知道我的利用目标应该是用printf()函数指针覆盖challenge()函数指针,但我似乎无法弄清楚如何实现该写入.我有以下要利用的代码,它使用的malloc是glibc 2.11.2:

void challenge()
{
        puts("you win\n");
}

int main(int argc, char **argv)
{
        char *inputA, *inputB, *inputC;

        inputA = malloc(32);
        inputB = malloc(32);
        inputC = malloc(32);

        strcpy(inputA, argv[1]);
        strcpy(inputB, argv[2]);
        strcpy(inputC, argv[3]);

        free(inputC);
        free(inputB);
        free(inputA);

        printf("execute challenge to win\n");
}

显然,实现对分配的块的元数据的实际覆盖是微不足道的.但是,我还没有找到使用任何标准技术来利用此代码的方法.我已阅读并试图实施以下技术:

• 论文:w00w00关于Heap Overflows
  • 尽管论文非常清楚,但该unlink技术已经过时了一段时间.
• Malloc Maleficarum.txt
  • 本文扩展了w00w00天的漏洞利用技术,并解释了glibc的新版本.但是,我没有发现,鉴于本文详述的5种技术,上述代码与这些技术的任何先决条件相匹配.
• 通过打破它来理解堆(pdf)
  • pdf非常好地回顾了堆的工作原理,但重点介绍了双重自由技术.

我最初试图通过操纵inputC的块的大小值来利用此代码,以便它指向inputC块的头部.当这不起作用时,我尝试进一步指向inputB的块.那时我意识到新的glibc会对大小值进行健全性检查.

如果用户能够将分配的块的元数据编辑为任意值,并使用它来覆盖GOT中的值或写入任何其他任意地址,那么用户如何利用免费利用漏洞利用？

注意:当我写"任意地址"据我所知,内存页面可能是只读或受保护的,我的意思是我可以假设我可以写一个地址.

我们收到了客户的本机(完整)故障转储文件.在Visual Studio(2005)调试器中打开它表明我们遇到了由试图分配~10MB块的realloc调用引起的崩溃.转储文件非常大(1.5 GB - 通常它们更像500 MB).

因此,我们得出结论,我们有一个内存"泄漏"或失控的分配,要么完全耗尽进程的内存,要么至少将其分散到足以使realloc失败.^{(请注意,这个realloc用于分配日志记录缓冲区的操作,我们并不感到惊讶它在这里失败,因为一次性使用10MB将是我们除了一些非常大的非常不可更改的缓冲区之外的更大分配之一 - 问题本身可能与此特定分配无关.)}

编辑:在下面的Lex Li评论交换之后,我应该补充:这对我们来说是不可再现的(此刻).这只是一个客户转储显然显示失控的内存消耗.

主要问题:

现在我们有一个转储文件,但是我们如何找到导致内存使用过多的原因？

到目前为止我们做了什么:

我们使用DebugDiag工具来分析转储文件(所谓的内存压力分析器),这是我们得到的:

Report for DumpFM...dmp

Virtual Memory Summary
----------------------
Size of largest free VM block   62,23 MBytes 
Free memory fragmentation       81,30% 
Free Memory                     332,87 MBytes   (16,25% of Total Memory) 
Reserved Memory                 0 Bytes   (0,00% of Total Memory) 
Committed Memory                1,67 GBytes   (83,75% of Total Memory) 
Total Memory                    2,00 GBytes 
Largest free block at           0x00000000`04bc4000 

Loaded Module Summary
---------------------
Number …

我正在阅读JVM调优,我发现JVM在执行GC时会继续移动对象.但Java对象之间相互引用,人们认为它们是作为指针实现的,但每次移动对象后,JVM都不可能遍历整个堆,并更新所有引用; 肯定会永远.那么它如何解析引用,如果引用没有改变,但对象的物理位置呢？

我已经阅读了很多关于JVM的内容,但在任何地方都没有解释,甚至暗示过.

[编辑]我的观点是,引用是单向的.从指针到指向是"瞬时",但反过来需要完整的堆扫描.虽然有可能,但似乎不太可能.如果10K对象在次要集合中存活,那么执行完整堆扫描需要多长时间才能更新对这些对象的引用10K次？必须使用某种优化的算法或结构.

我是Windows编程的新手,我只是"迷失"两个小时寻找一个每个人都知道的错误:你不能在DLL中创建一个对象并在另一个DLL(或主程序)中销毁它.

我几乎可以肯定,在Linux/Unix上,情况并非如此(如果是的话,请说出来,但我很确定我做了数千次而没有问题......).

在这一点上,我有几个问题:

1)静态链接的DLL使用与主程序不同的堆吗？

2)静态链接的DLL是否映射在主程序的同一进程空间中？(我很确定这里的答案是一个很大的问题,否则将主程序中的函数指针传递给DLL中的函数是没有意义的.)

我说的是普通/常规DLL,而不是COM/ATL服务

编辑:通过"静态链接"我的意思是我不使用LoadLibrary加载DLL但我链接到存根库

我的问题来自下面的leetcode解决方案,我无法理解为什么会这样O(k+(n-k)log(k)).

补充:也许复杂性不是那样,实际上我不知道时间的复杂性heappush()和heappop()

# O(k+(n-k)lgk) time, min-heap
def findKthLargest(self, nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    for _ in xrange(len(nums)-k):
        heapq.heappop(heap)
    return heapq.heappop(heap)

我正在阅读CLRS第三版中的 Dijkstra算法(第662页).这是我不明白的书中的一部分:

如果图形足够稀疏 - 特别是E = o(V^2/lg V)- 我们可以通过使用二进制最小堆实现最小优先级队列来改进算法.

图为什么要稀疏？

这是另一部分:

每个DECREASE-KEY操作都需要时间O(log V),并且最多仍然有E这样的操作.

假设我的图形如下所示:

我想计算从1到6的最短路径并使用最小堆方法.首先,我将所有节点添加到最小优先级队列.构建最小堆后,min节点是源节点(因为它与自身的距离为0).我提取它并更新其所有邻居的距离.

然后我需要调用decreaseKey距离最小的节点来创建一个新的最小堆.但是如何在恒定时间内知道它的指数呢？

节点

private static class Node implements Comparable<Node> {

    final int key;
    int distance = Integer.MAX_VALUE;
    Node prev = null;

    public Node(int key) {
        this.key = key;
    }

    @Override
    public int compareTo(Node o) {
        if (distance < o.distance) {
            return -1;
        } else if (distance > o.distance) {
            return 1;
        } else {
            return 0;
        }
    }

    @Override …