C语言是否可以恢复单个链表的头部指针?

如果可以做出以下假设，是否可以恢复链表的头节点。

链表是使用 malloc 创建的，可以从堆区域访问它。
堆开始和结束地址可以从/proc/self/maps 中找到(至少在 Linux 中(。
原始链表中至少有一个节点是可访问的。
指向前一个节点的指针将在堆中的某处找到。
并且可以递归搜索，直到找到实际的头部。

为了更好地说明它，请使用以下程序，该程序可以在默认配置下至少在 Ubuntu/WSL 下使用 gcc 成功编译。

程序

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
typedef struct node
{
int val;
struct node *next;
} node_t;
node_t *head = NULL;
unsigned long start_address = 0;
unsigned long end_address = 0;
node_t *getLastNode()
{
node_t *iter = head;
for (; iter->next != NULL; iter = iter->next)
;
return iter;
}
void addToLinkedList(int value)
{
node_t *data = malloc(sizeof(node_t));
data->val = value;
data->next = NULL;
if (head == NULL)
head = data;
else
getLastNode()->next = data;
}
void createLinkedList()
{
// Add 10 nodes to the linked list
int start_val = 0x10101010;
for (int i = 1; i <= 10; i++)
addToLinkedList(start_val * i);
}
void printLinkedList()
{
printf("Head pointer of Linked List : %pn", head);
for (node_t *iter = head; iter != NULL; iter = iter->next)
printf("%p -> value = %X, next = %p n", iter, iter->val, iter->next);
printf("n");
}
void resetHeadPtr()
{
// Lets make head point to the last node
head = getLastNode();
}
void findHeapBoundary()
{
// Code inspired from https://unix.stackexchange.com/a/251769/152334
char mapsFilename[1024];
char line[256];
char area[1024];
sprintf(mapsFilename, "/proc/%d/maps", getpid());
FILE *pMapsFile = fopen(mapsFilename, "r");
while (fgets(line, 256, pMapsFile) != NULL)
{
// Dirty hack to get the heap start and end address
sscanf(line, "%08lx-%08lx%*[^[]%sn", &start_address, &end_address, area);
if (strcmp(area, "[heap]") == 0)
break;
}
fclose(pMapsFile);
printf("Heap memory start address : %pn", (int *)start_address);
printf("Heap memory end address   : %pn", (int *)end_address);
}
node_t *findPointerInMemory()
{
for (int *ptr = (int *)start_address; ptr < (int *)(end_address - sizeof(node_t)); ptr++)
{
if (((node_t *)ptr)->next == head)
return (node_t *)ptr;
}
return NULL;
}
void recoverHeadPtr()
{
node_t *ptr = findPointerInMemory();
if (ptr == NULL)
{
printf("Cannot find %p in heap memorynStopping Searchnn", head);
return;
}
printf("Found %p at %pn", head, ptr);
head = ptr;
recoverHeadPtr();
}
int main(int argc, char const *argv[])
{
createLinkedList();
printf("Original Linked List Contentsn*****************************n");
printLinkedList();
resetHeadPtr();
printf("Linked List Contents after resetn********************************n");
printLinkedList();
findHeapBoundary();
recoverHeadPtr();
printf("Recovered Linked List Contentsn******************************n");
printLinkedList();
return 0;
}

输出

Original Linked List Contents
*****************************
Head pointer of Linked List : 0x1db6010
0x1db6010 -> value = 10101010, next = 0x1db6030
0x1db6030 -> value = 20202020, next = 0x1db6050
0x1db6050 -> value = 30303030, next = 0x1db6070
0x1db6070 -> value = 40404040, next = 0x1db6090
0x1db6090 -> value = 50505050, next = 0x1db60b0
0x1db60b0 -> value = 60606060, next = 0x1db60d0
0x1db60d0 -> value = 70707070, next = 0x1db60f0
0x1db60f0 -> value = 80808080, next = 0x1db6110
0x1db6110 -> value = 90909090, next = 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)
Linked List Contents after reset
********************************
Head pointer of Linked List : 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)
Heap memory start address : 0x1db6000
Heap memory end address   : 0x1dd7000
Found 0x1db6130 at 0x1db6110
Found 0x1db6110 at 0x1db60f0
Found 0x1db60f0 at 0x1db60d0
Found 0x1db60d0 at 0x1db60b0
Found 0x1db60b0 at 0x1db6090
Found 0x1db6090 at 0x1db6070
Found 0x1db6070 at 0x1db6050
Found 0x1db6050 at 0x1db6030
Found 0x1db6030 at 0x1db6010
Cannot find 0x1db6010 in heap memory
Stopping Search
Recovered Linked List Contents
******************************
Head pointer of Linked List : 0x1db6010
0x1db6010 -> value = 10101010, next = 0x1db6030
0x1db6030 -> value = 20202020, next = 0x1db6050
0x1db6050 -> value = 30303030, next = 0x1db6070
0x1db6070 -> value = 40404040, next = 0x1db6090
0x1db6090 -> value = 50505050, next = 0x1db60b0
0x1db60b0 -> value = 60606060, next = 0x1db60d0
0x1db60d0 -> value = 70707070, next = 0x1db60f0
0x1db60f0 -> value = 80808080, next = 0x1db6110
0x1db6110 -> value = 90909090, next = 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)

背景

我的一个朋友在一次采访中被问到以下问题。"如果给定最后一个节点，你能找到单个链表的头指针吗？"他回答"没有"，尽管面试官对答案并不完全满意，但他还是得到了这份工作。这让我开始思考，是否有可能这样做。

所以，真正的问题是。

这种方法正确吗？
我们需要在其他内存段中搜索吗？
这种方法也可以推广到Windows上吗？
ASLR会对这种方法产生任何影响吗？

正确答案是：

不干净，尝试这样做对于糟糕的设计来说将是一个有风险的解决方法。
如果您确实尝试在内存中搜索任何内容的地址(如果它是有问题的指针，则不能以任何方式保证仅包含该地址(，那么您可能会发现任何似乎意外包含看起来像相关地址的数字的内存。
如果你继续使用它，假设它是指针，你就招致了各种各样的问题。
如果你反复这样做以倒退单链表，那么你几乎可以保证至少找到一个废话。

简而言之：没有。

一个简单的"不"太短了，可能会因此而让考官皱起眉头。

在标准 C 中这是不可能的。

通过 malloc 提供的指针(或这些指针的副本等(以外的方式访问堆会让你获得未定义的行为。

但是，如果您了解分配器并且可以遍历分配的内存块的结构，则可以找到候选列表节点。其中之一将是头部。

相关内容

最新更新

热门标签：

C语言 是否可以恢复单个链表的头部指针?

相关内容

最新更新

热门标签：

C语言是否可以恢复单个链表的头部指针?