malloc指針識別

所以我有這個任務來實現我自己的malloc並在C中免費。這個問題是memory_free(void *ptr)函數的要求之一。如果指針無效，它必須返回1，即它沒有被memory_alloc(unsigned int size)分配，否則返回0。我只是無法想出一個辦法來做到這一點，沒有絕對時間效率低下。malloc指針識別

所以我的內存結構是這樣的：我有一個全局指針指向數組的開始，我可以充當堆。每個內存塊都有一個int頭文件來說明它的大小以及它是否空閒。

這是我memory_free（無效* PTR）的功能，現在，TYPE是typedef unsigned int：

int memory_free(void *ptr) 
{ 
    void *head = ptr; 
    if (head == NULL) 
     return 1; 
    head -= sizeof(TYPE); 
    if (!((*(TYPE*) head) & 1)) 
     return 1; 
    (*(TYPE*) head) &= ~0x1; 
    return 0; 
}

指針ptr點到用戶塊的第一個字節，這意味着如果我想讀頭，我必須返回4個字節。檢查指針有效性的一種解決方案是從頭開始查看堆，然後看看我是否遇到了標題，但這不是時間效率高的。誰能告訴我更好的方法？

來源

2014-10-10 Slaaavo

這段代碼到底有多嚴重？我看起來很有效率。主要關心的是代碼看起來完全不安全。如果沒有某種查找表記錄實際存在的內存塊，我不會實現動態內存分配算法。如果指針指向隨機垃圾會怎麼樣？如果用戶錯誤地在同一對象上調用memory_free兩次會怎麼樣？ – Lundin 2014-10-10 13:28:18

這就是我的問題。我不得不在每次調用memory_free時都進行測試。這就是我的問題:)。要明確，我現在基本上不檢查它，因爲這些條件在一半時間內都是成功的。 – Slaaavo 2014-10-10 13:30:43

如果是這樣，你如何期望任何人能夠回答，而不提供有關你如何分配和跟蹤記憶的信息？ – Lundin 2014-10-10 13:36:04

一個O（1）解決方案將使標題8字節而不是4;使用額外的四個字節來表示有效性。例如，它可能是您在其他四個字節中存儲的內容的補充。所以你看看頭文件，如果這些額外的字節包含除頭標第一部分的補碼以外的任何內容，那麼你知道這不是一個有效的塊。

來源

2014-10-10 13:21:35

這種方法似乎有一個缺陷：設想調用'ptr = memory_alloc（64）'，然後用戶代碼寫入該區域，然後調用'memory_free（ptr + 32）'。這樣分配者就可以被「欺騙」去思考。 – 2014-10-10 13:24:46

好吧，當然。大多數malloc可以很容易地通過這種方式「欺騙」。 – 2014-10-10 13:30:44

'free'不必檢查其論證的有效性;傳遞未被'（m | c | re）alloc'返回的指針是未定義的行爲。 – 2014-10-10 13:31:45

我看到2點可能的選擇：

保留已分配的指針鏈表：由memory_alloc填充和memory_free消耗。通過這種方式，您可以仔細檢查傳遞給memory_free的內容是否一致。
鏈表可能非常耗時：作爲折衷方案，您可以只存儲內存池的開始和結束地址，並確保傳遞給memory_free的指針處於正確的範圍內。它的精確度和可靠性要低得多

來源

2014-10-10 14:06:30 Coconop

問題是，當在分配器中使用鏈表時，你仍然必須分配每個節點。我會建議一個塊的鏈表，其中每個塊包含一些不變數量的指針。 – 2014-10-10 14:26:08

在他的問題中，他似乎已經摒棄了O（N）解決方案，因爲效率太低 - 他不想掃描一個列表。 – 2014-10-10 14:34:20

也有跳過列表是'O（log N）'。另外，正如我已經說過的，一個bitvector可以加快查找數量級。 – 2014-10-10 14:38:24

malloc指針識別

回答

相關問題