If you are writing code on Linux, valgrind is a nice handy tool to help to detect memory leaks for a program, but what if you are on macOS. There are also many similar tools, graphical user interface tools or command line tools. leaks is a nice handy command tool.
Let’s learn by example, here, let’s use leetcode 2. Add Two Numbers. The problem says “
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
“
Here is the code which can pass the online test:
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* dummyNode = new ListNode();
ListNode* temp = dummyNode;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = 0;
if (l1)
{
sum += l1->val;
l1 = l1->next;
}
if (l2)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
temp->next = node;
temp = temp->next;
}
return dummyNode->next;
}
};But have you noticed that there is memory leak. It’s easy to find it out in this case, we allocate a dummyNode at the beginning of this function, but not deallocate it. Let’s fix it.
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode dummyNode;
ListNode* temp = &dummyNode;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = 0;
if (l1)
{
sum += l1->val;
l1 = l1->next;
}
if (l2)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
temp->next = node;
temp = temp->next;
}
return dummyNode.next;
}
};This time, the dummyNode will be automatically destroyed, but there are still memory leaks, the ListNode allocated in the while loop are never deleted. Let’s fix it this way:
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode dummyNode;
ListNode* temp = &dummyNode;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = 0;
if (l1)
{
sum += l1->val;
l1 = l1->next;
}
if (l2)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
temp->next = node;
temp = temp->next;
}
_head = dummyNode.next;
return _head;
}
~Solution()
{
if (!_head) return;
std::vector<ListNode*> nodes;
while(_head)
{
nodes.push_back(_head);
_head = _head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
delete nodes[i];
}
private:
ListNode* _head {};
};When we run it, we got this. This means that the online judgement system will manage the corresponding heap memory, so we don’t have to handle it actually. We just need to deal with the algorithm itself.
But what if we write the entire thing by ourself, here is the code:
// compile with: g++ -Wall -std=c++20 -o prog.out main.cc
#include <iostream>
#include <string>
#include <vector>
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int val) : val(val), next(nullptr) {}
ListNode(int val, ListNode* next) : val(val), next(next) {}
};
class ILinkedList
{
public:
virtual ListNode* getHead() const { return nullptr; }
virtual ~ILinkedList() {};
};
class LinkedList1 final : public ILinkedList
{
public:
explicit LinkedList1(const std::vector<int>& input)
{
_head = makeList(input);
}
~LinkedList1()
{
destroyList();
}
ListNode* getHead() const override
{
return _head;
}
private:
ListNode* makeList(const std::vector<int>& input)
{
int n = input.size();
if (n == 0) return nullptr;
ListNode* head = new ListNode(input[0]);
ListNode* nodes[n];
nodes[0] = head;
int i = 1;
while(i < n)
{
ListNode* node = new ListNode(input[i]);
nodes[i++] = node;
}
for (int i = 0; i < n; ++i)
nodes[i]->next = i + 1 == n ? nullptr : nodes[i+1];
return nodes[0];
}
void destroyList()
{
if (!_head) return;
std::vector<ListNode*> nodes;
while(_head)
{
nodes.push_back(_head);
_head = _head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
delete nodes[i];
}
private:
ListNode* _head;
};
class LinkedListFactory
{
LinkedListFactory() = default;
public:
static ILinkedList* make(const std::vector<int>& input)
{
LinkedList1* linkedList = new LinkedList1(input);
static LinkedListFactory s_Instance;
s_Instance._lists.push_back(linkedList);
return linkedList;
}
static void destoryList(ListNode* head)
{
if (!head) return;
std::vector<ListNode*> nodes;
while(head)
{
nodes.push_back(head);
head = head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
{
delete nodes[i];
nodes[i] = nullptr;
}
}
static std::vector<int> getListValues(ListNode* head)
{
std::vector<int> ans;
if (!head) return ans;
while(head)
{
ans.push_back(head->val);
head = head->next;
}
return ans;
}
~LinkedListFactory()
{
for (auto& list : _lists)
delete list;
}
private:
std::vector<ILinkedList*> _lists;
};
class Solution
{
public:
// time complexity: O(max(l1,l2)), space: O(n)
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode dummyNode;
ListNode* temp = &dummyNode;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = 0;
if (l1)
{
sum += l1->val;
l1 = l1->next;
}
if (l2)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
temp->next = node;
temp = temp->next;
}
return dummyNode.next;
}
};
void test0()
{
std::vector<int> list1 = { 2, 4, 3 };
std::vector<int> list2 = { 5, 6, 4 };
const std::vector<int> expected = { 7, 0, 8 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void test1()
{
std::vector<int> list1 = { 0 };
std::vector<int> list2 = { 0 };
const std::vector<int> expected = { 0 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void test2()
{
std::vector<int> list1 = { 9, 9, 9, 9, 9, 9, 9 };
std::vector<int> list2 = { 9, 9, 9, 9 };
const std::vector<int> expected = { 8, 9, 9, 9, 0, 0, 0, 1 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void runTests()
{
test0();
test1();
test2();
}
int main()
{
runTests();
return 0;
}When we run the program, all 3 cases pass. Let’s run it with leaks command to see what’s going on. Here is the output:
$ leaks --atExit -- ./prog.out
Pass
Pass
Pass
Process: prog.out [73145]
Path: /path/to/prog.out
Load Address: 0x10f9fc000
Identifier: prog.out
Version: ???
Code Type: X86-64
Platform: macOS
Parent Process: leaks [73144]
Date/Time: 2023-10-11 17:43:19.440 -0700
Launch Time: 2023-10-11 17:43:19.389 -0700
OS Version: macOS 12.6.8 (21G725)
Report Version: 7
Analysis Tool: /usr/bin/leaks
Physical footprint: 2096K
Physical footprint (peak): 2096K
----
leaks Report Version: 4.0
Process 73145: 180 nodes malloced for 13 KB
Process 73145: 12 leaks for 192 total leaked bytes.
12 (192 bytes) << TOTAL >>
8 (128 bytes) ROOT LEAK: 0x60000121c220 [16]
7 (112 bytes) 0x60000121c230 [16] length: 1 " "
6 (96 bytes) 0x60000121c240 [16] length: 1 " "
5 (80 bytes) 0x60000121c250 [16] length: 1 " "
4 (64 bytes) 0x60000121c260 [16]
3 (48 bytes) 0x60000121c270 [16]
2 (32 bytes) 0x60000121c280 [16]
1 (16 bytes) 0x60000121c290 [16]
3 (48 bytes) ROOT LEAK: 0x60000121c0b0 [16]
2 (32 bytes) 0x60000121c110 [16]
1 (16 bytes) 0x60000121c120 [16]
1 (16 bytes) ROOT LEAK: 0x60000121c160 [16]We can see there are 12 leaks, we know they are from the Solution class, because it is obvious, but when our code becomes large, how can we tell where the leaks come from. Here is the trick, we can enable a flag for leaks command, so that it can output more details.
export MallocStackLogging=1Run it one more time, we got this:
$ leaks --atExit --list -- ./prog.out
leaks(73200) MallocStackLogging: could not tag MSL-related memory as no_footprint, so those pages will be included in process footprint - (null)
leaks(73200) MallocStackLogging: stack logs being written to /private/tmp/stack-logs.73200.105213000.leaks.tT0m8K.index
leaks(73200) MallocStackLogging: recording malloc and VM allocation stacks to disk using standard recorder
prog.out(73201) MallocStackLogging: could not tag MSL-related memory as no_footprint, so those pages will be included in process footprint - (null)
prog.out(73201) MallocStackLogging: stack logs being written to /private/tmp/stack-logs.73201.10ec52000.prog.out.JQPpwe.index
prog.out(73201) MallocStackLogging: recording malloc and VM allocation stacks to disk using standard recorder
Pass
Pass
Pass
prog.out(73201) MallocStackLogging: stack logs deleted from /private/tmp/stack-logs.73201.10ec52000.prog.out.JQPpwe.index
Process: prog.out [73201]
Path: /path/to/prog.out
Load Address: 0x10eb14000
Identifier: prog.out
Version: 0
Code Type: X86-64
Platform: macOS
Parent Process: leaks [73200]
Date/Time: 2023-10-11 17:48:35.430 -0700
Launch Time: 2023-10-11 17:48:35.242 -0700
OS Version: macOS 12.6.8 (21G725)
Report Version: 7
Analysis Tool: /usr/bin/leaks
Physical footprint: 3116K
Physical footprint (peak): 3120K
----
leaks Report Version: 3.0
Process 73201: 182 nodes malloced for 13 KB
Process 73201: 12 leaks for 192 total leaked bytes.
Leak: 0x600001b1c080 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb16399 (prog.out) runTests() | 0x10eb1576a (prog.out) test0() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c0e0 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb16399 (prog.out) runTests() | 0x10eb1576a (prog.out) test0() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c0f0 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb16399 (prog.out) runTests() | 0x10eb1576a (prog.out) test0() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c130 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb1639e (prog.out) runTests() | 0x10eb15ef8 (prog.out) test1() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c1f0 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c200 size=16 zone: DefaultMallocZone_0x10ec4a000 length: 1 " "
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c210 size=16 zone: DefaultMallocZone_0x10ec4a000 length: 1 " "
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c220 size=16 zone: DefaultMallocZone_0x10ec4a000 length: 1 " "
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c230 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c240 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c250 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Leak: 0x600001b1c260 size=16 zone: DefaultMallocZone_0x10ec4a000
Call stack: 0x119c6252e (dyld) start | 0x10eb163c4 (prog.out) main | 0x10eb163a3 (prog.out) runTests() | 0x10eb161eb (prog.out) test2() | 0x10eb15b03 (prog.out) Solution::addTwoNumbers(ListNode*, ListNode*) | 0x7ff819db995a (libc++abi.dylib) operator new(unsigned long) | 0x7ff819c33b37 (libsystem_malloc.dylib) _malloc_zone_malloc
Binary Images:
0x10eb14000 - 0x10eb1bfff +prog.out (0) <0B58EBFF-7E8A-3250-AD2D-8B40916F9594> /Users/*/Documents/*/prog.out
0x10ec59000 - 0x10ec5cfff libLeaksAtExit.dylib (64552.23.1) <CC3C8D85-B0DE-3445-85BE-85111E9CC36F> /usr/lib/libLeaksAtExit.dylib
0x119c5d000 - 0x119cc6567 dyld (960) <BAAB2C6D-3797-3264-8595-A591561979DE> /usr/lib/dyld
0x7ff819b2d000 - 0x7ff819b2eff2 libsystem_blocks.dylib (79.1) <CE5E8C55-9E28-3982-9B98-74230BAD820F> /usr/lib/system/libsystem_blocks.dylib
0x7ff819b2f000 - 0x7ff819b6afff libxpc.dylib (2236.140.2.701.2) <F791F5E1-708F-3B18-A112-BD538AACFD66> /usr/lib/system/libxpc.dylib
0x7ff819b6b000 - 0x7ff819b83ffe libsystem_trace.dylib (1375.140.2) <F0EF1345-060A-3065-A399-B1A2F89C5D12> /usr/lib/system/libsystem_trace.dylib
0x7ff819b84000 - 0x7ff819c15fe7 libcorecrypto.dylib (1218.120.10) <AEA09B4E-2C67-383C-9BE7-5C13E1A984B4> /usr/lib/system/libcorecrypto.dylib
0x7ff819c16000 - 0x7ff819c41fff libsystem_malloc.dylib (374.120.1) <47042ACD-A337-322A-8DB7-ECD59CC60D92> /usr/lib/system/libsystem_malloc.dylib
0x7ff819c42000 - 0x7ff819c88ffb libdispatch.dylib (1325.120.2) <1A04B380-76E4-3E4B-B0FC-9837533D021D> /usr/lib/system/libdispatch.dylib
0x7ff819c89000 - 0x7ff819cc2ff2 libobjc.A.dylib (841.13) <4D9B0DCA-7151-3875-B98E-B255DB8267A8> /usr/lib/libobjc.A.dylib
0x7ff819cc3000 - 0x7ff819cc5ff7 libsystem_featureflags.dylib (56) <CAB9769A-0B25-311F-A2CB-375105985D22> /usr/lib/system/libsystem_featureflags.dylib
0x7ff819cc6000 - 0x7ff819d4eff7 libsystem_c.dylib (1507.100.9) <E42E9D7A-03B4-340B-B61E-DCD45FD4ACC0> /usr/lib/system/libsystem_c.dylib
0x7ff819d4f000 - 0x7ff819da7ff7 libc++.1.dylib (1300.36) <A031469A-A9FE-37E0-8523-4F80351EA635> /usr/lib/libc++.1.dylib
0x7ff819da8000 - 0x7ff819dbdff7 libc++abi.dylib (1300.36) <A99F1FB2-FD31-3CF4-BE4D-A9FCCF219974> /usr/lib/libc++abi.dylib
0x7ff819dbe000 - 0x7ff819df5fff libsystem_kernel.dylib (8020.240.18.702.13) <5E9789AF-5BCA-3E41-A07A-C2DCC3180EA3> /usr/lib/system/libsystem_kernel.dylib
0x7ff819df6000 - 0x7ff819e01ff7 libsystem_pthread.dylib (486.100.11.701.1) <E5D44AFD-2577-3CEE-8711-9D8D426229E0> /usr/lib/system/libsystem_pthread.dylib
0x7ff819e02000 - 0x7ff819e0dfff libdyld.dylib (960) <64C284B3-231B-391D-845C-A285DFA305CD> /usr/lib/system/libdyld.dylib
0x7ff819e0e000 - 0x7ff819e17fef libsystem_platform.dylib (273.100.5) <A8A33774-6D44-35E9-AD2A-BAD9E4D5192A> /usr/lib/system/libsystem_platform.dylib
0x7ff819e18000 - 0x7ff819e42fff libsystem_info.dylib (554.120.2) <6D4B0DA7-8EFC-3E6D-B984-F49260C3C194> /usr/lib/system/libsystem_info.dylib
0x7ff81c439000 - 0x7ff81c442fff libsystem_darwin.dylib (1507.100.9) <C8C06B65-C4DF-3C86-8D03-ACB8568EC261> /usr/lib/system/libsystem_darwin.dylib
0x7ff81c85f000 - 0x7ff81c86dfff libsystem_notify.dylib (301) <8FDAD401-BF94-33BD-AC95-6928272AF18D> /usr/lib/system/libsystem_notify.dylib
0x7ff81ed31000 - 0x7ff81ed47ffb libsystem_networkextension.dylib (1471.141.3.701.1) <7C1B8F57-E37C-3C62-B142-B4824EB70627> /usr/lib/system/libsystem_networkextension.dylib
0x7ff81ed96000 - 0x7ff81edacff7 libsystem_asl.dylib (392.100.2) <4C84DA5F-6450-3B33-8CA5-E6775EB3C7BB> /usr/lib/system/libsystem_asl.dylib
0x7ff8205e4000 - 0x7ff8205ebfff libsystem_symptoms.dylib (1617.140.3) <643A7FA0-DC38-30CF-B755-8FFE9A768B30> /usr/lib/system/libsystem_symptoms.dylib
0x7ff822768000 - 0x7ff822784ffb libsystem_containermanager.dylib (383.120.2.700.1) <D4B1407C-B6DD-3A8E-A439-46FC50C10726> /usr/lib/system/libsystem_containermanager.dylib
0x7ff8234be000 - 0x7ff8234c1ffb libsystem_configuration.dylib (1163.140.3) <C8A8DB1F-A66B-3AB8-88F8-D3F81E13952F> /usr/lib/system/libsystem_configuration.dylib
0x7ff8234c2000 - 0x7ff8234c7ff3 libsystem_sandbox.dylib (1657.240.4.701.2) <34F0CF85-744C-3CC1-9B93-FCA30807A1D8> /usr/lib/system/libsystem_sandbox.dylib
0x7ff82420a000 - 0x7ff82420cff7 libquarantine.dylib (133.120.2) <DE4AFED5-17A7-3BBE-BC74-F59B0119F8BA> /usr/lib/system/libquarantine.dylib
0x7ff8248c1000 - 0x7ff8248c5fff libsystem_coreservices.dylib (133) <8C364FD4-92EB-3D96-903B-23556015AD00> /usr/lib/system/libsystem_coreservices.dylib
0x7ff824b27000 - 0x7ff824b87fd7 libsystem_m.dylib (3204.80.2) <5873BB02-9C24-330E-BE3F-A69937620E64> /usr/lib/system/libsystem_m.dylib
0x7ff824b89000 - 0x7ff824b8efff libmacho.dylib (994) <1A2B574F-0D91-376B-8122-C9915A89B719> /usr/lib/system/libmacho.dylib
0x7ff824bab000 - 0x7ff824bb6ff7 libcommonCrypto.dylib (60191.100.1) <1A00FE13-7DED-3B41-9655-EF210F31764E> /usr/lib/system/libcommonCrypto.dylib
0x7ff824bb7000 - 0x7ff824bc1fff libunwind.dylib (202.2) <079E4280-10E2-3062-BC91-A190F3A0C07E> /usr/lib/system/libunwind.dylib
0x7ff824bc2000 - 0x7ff824bc9fff liboah.dylib (254.25) <AFA80743-2279-362C-A4A4-F17A5C10806F> /usr/lib/liboah.dylib
0x7ff824bca000 - 0x7ff824bd3fff libcopyfile.dylib (180.100.3) <3F9E168D-0697-3311-86DE-63884A75299C> /usr/lib/system/libcopyfile.dylib
0x7ff824bd4000 - 0x7ff824bdbfff libcompiler_rt.dylib (103.1) <C0F60CA9-4403-3539-8B35-FCDC19CDDCAD> /usr/lib/system/libcompiler_rt.dylib
0x7ff824bdc000 - 0x7ff824be0ff7 libsystem_collections.dylib (1507.100.9) <D3FEAEB6-20E5-316C-87CA-DAE981459D66> /usr/lib/system/libsystem_collections.dylib
0x7ff824be1000 - 0x7ff824be3ff7 libsystem_secinit.dylib (107.100.5) <1073080D-83EA-3190-AB3F-F299FC7C042E> /usr/lib/system/libsystem_secinit.dylib
0x7ff824be4000 - 0x7ff824be5fff libremovefile.dylib (60) <0A06ABF0-FA65-3ADA-A46A-A6F7C62F5C15> /usr/lib/system/libremovefile.dylib
0x7ff824be6000 - 0x7ff824be6ffb libkeymgr.dylib (31) <16BAFDE1-B1FC-3A4B-B06B-709AB4E357AB> /usr/lib/system/libkeymgr.dylib
0x7ff824be7000 - 0x7ff824beefff libsystem_dnssd.dylib (1557.140.5.0.1) <1DFA63CE-158B-3B32-A6BD-9881C2B4045E> /usr/lib/system/libsystem_dnssd.dylib
0x7ff824bef000 - 0x7ff824bf3fff libcache.dylib (85) <54431C2C-7EBD-3E17-AEA3-9A7FFD3403AC> /usr/lib/system/libcache.dylib
0x7ff824bf4000 - 0x7ff824bf5fff libSystem.B.dylib (1311.120.1) <93013FDD-428E-3265-A80F-8544E2DB7CD7> /usr/lib/libSystem.B.dylib
0x7ff82ae68000 - 0x7ff82ae68fff libsystem_product_info_filter.dylib (10) <27C0A669-AF41-38F3-AF68-B4DE8FFD5128> /usr/lib/system/libsystem_product_info_filter.dylib
0x7ff920122000 - 0x7ff920131ff7 com.apple.MallocStackLogging (1.0 - 1) <409AC2F0-F32B-3457-B952-994E940C140A> /System/Library/PrivateFrameworks/MallocStackLogging.framework/Versions/A/MallocStackLogging
leaks(73200) MallocStackLogging: stack logs deleted from /private/tmp/stack-logs.73200.105213000.leaks.tT0m8K.indexFrom the verbose log, we can see the leak is in the Solution::addTwoNumbers function, so we add back our Solution class destructor, here is the full code:
// compile with: g++ -Wall -std=c++20 -o prog.out main.cc
#include <iostream>
#include <string>
#include <vector>
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int val) : val(val), next(nullptr) {}
ListNode(int val, ListNode* next) : val(val), next(next) {}
};
class ILinkedList
{
public:
virtual ListNode* getHead() const { return nullptr; }
virtual ~ILinkedList() {};
};
class LinkedList1 final : public ILinkedList
{
public:
explicit LinkedList1(const std::vector<int>& input)
{
_head = makeList(input);
}
~LinkedList1()
{
destroyList();
}
ListNode* getHead() const override
{
return _head;
}
private:
ListNode* makeList(const std::vector<int>& input)
{
int n = input.size();
if (n == 0) return nullptr;
ListNode* head = new ListNode(input[0]);
ListNode* nodes[n];
nodes[0] = head;
int i = 1;
while(i < n)
{
ListNode* node = new ListNode(input[i]);
nodes[i++] = node;
}
for (int i = 0; i < n; ++i)
nodes[i]->next = i + 1 == n ? nullptr : nodes[i+1];
return nodes[0];
}
void destroyList()
{
if (!_head) return;
std::vector<ListNode*> nodes;
while(_head)
{
nodes.push_back(_head);
_head = _head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
delete nodes[i];
}
private:
ListNode* _head;
};
class LinkedListFactory
{
LinkedListFactory() = default;
public:
static ILinkedList* make(const std::vector<int>& input)
{
LinkedList1* linkedList = new LinkedList1(input);
static LinkedListFactory s_Instance;
s_Instance._lists.push_back(linkedList);
return linkedList;
}
static void destoryList(ListNode* head)
{
if (!head) return;
std::vector<ListNode*> nodes;
while(head)
{
nodes.push_back(head);
head = head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
{
delete nodes[i];
nodes[i] = nullptr;
}
}
static std::vector<int> getListValues(ListNode* head)
{
std::vector<int> ans;
if (!head) return ans;
while(head)
{
ans.push_back(head->val);
head = head->next;
}
return ans;
}
~LinkedListFactory()
{
for (auto& list : _lists)
delete list;
}
private:
std::vector<ILinkedList*> _lists;
};
class Solution
{
public:
// time complexity: O(max(l1,l2)), space: O(n)
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode dummyNode;
ListNode* temp = &dummyNode;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = 0;
if (l1)
{
sum += l1->val;
l1 = l1->next;
}
if (l2)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
temp->next = node;
temp = temp->next;
}
_head = dummyNode.next;
return _head;
}
~Solution()
{
if (!_head) return;
std::vector<ListNode*> nodes;
while(_head)
{
nodes.push_back(_head);
_head = _head->next;
}
for (int i = nodes.size() - 1; i >= 0; --i)
delete nodes[i];
}
private:
ListNode* _head {};
};
void test0()
{
std::vector<int> list1 = { 2, 4, 3 };
std::vector<int> list2 = { 5, 6, 4 };
const std::vector<int> expected = { 7, 0, 8 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void test1()
{
std::vector<int> list1 = { 0 };
std::vector<int> list2 = { 0 };
const std::vector<int> expected = { 0 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void test2()
{
std::vector<int> list1 = { 9, 9, 9, 9, 9, 9, 9 };
std::vector<int> list2 = { 9, 9, 9, 9 };
const std::vector<int> expected = { 8, 9, 9, 9, 0, 0, 0, 1 };
ListNode* l1 = LinkedListFactory::make(list1)->getHead();
ListNode* l2 = LinkedListFactory::make(list2)->getHead();
Solution s;
ListNode* addedList = s.addTwoNumbers(l1, l2);
std::vector<int> ret = LinkedListFactory::getListValues(addedList);
std::cout << (expected == ret ? "Pass" : "Fail") << std::endl;
}
void runTests()
{
test0();
test1();
test2();
}
int main()
{
runTests();
return 0;
}Compile and run it one more time, no leaks anymore:
$ leaks --atExit --list -- ./prog.out
leaks(73386) MallocStackLogging: could not tag MSL-related memory as no_footprint, so those pages will be included in process footprint - (null)
leaks(73386) MallocStackLogging: stack logs being written to /private/tmp/stack-logs.73386.10c012000.leaks.cJHFf2.index
leaks(73386) MallocStackLogging: recording malloc and VM allocation stacks to disk using standard recorder
prog.out(73387) MallocStackLogging: could not tag MSL-related memory as no_footprint, so those pages will be included in process footprint - (null)
prog.out(73387) MallocStackLogging: stack logs being written to /private/tmp/stack-logs.73387.10ef6c000.prog.out.4W8b2e.index
prog.out(73387) MallocStackLogging: recording malloc and VM allocation stacks to disk using standard recorder
Pass
Pass
Pass
prog.out(73387) MallocStackLogging: stack logs deleted from /private/tmp/stack-logs.73387.10ef6c000.prog.out.4W8b2e.index
Process: prog.out [73387]
Path: /path/to/prog.out
Load Address: 0x10ee2e000
Identifier: prog.out
Version: 0
Code Type: X86-64
Platform: macOS
Parent Process: leaks [73386]
Date/Time: 2023-10-11 18:04:11.198 -0700
Launch Time: 2023-10-11 18:04:10.679 -0700
OS Version: macOS 12.6.8 (21G725)
Report Version: 7
Analysis Tool: /usr/bin/leaks
Physical footprint: 3148K
Physical footprint (peak): 3152K
----
leaks Report Version: 3.0
Process 73387: 170 nodes malloced for 13 KB
Process 73387: 0 leaks for 0 total leaked bytes.
leaks(73386) MallocStackLogging: stack logs deleted from /private/tmp/stack-logs.73386.10c012000.leaks.cJHFf2.indexThat’s it. BTW, here is the tips from Apple.
Tips for Improving Leak Detection
The following guidelines can help you find memory leaks quickly in your program. Most of these guidelines are intended to be used with the leaks tool but some are also applicable for general use.
- Run
leaksduring unit testing. Because unit testing exercises all code paths in a repeatable manner, you are more likely to find leaks than you would be if you were testing your code in a production environment. - Use the
-excludeoption ofleaksto filter out leaks in functions with known memory leaks. This option helps reduce the amount of extraneous information reported byleaks. - If
leaksreports a leak intermittently, set up a loop around the target code path and run the code hundreds or thousands of times. This increases the likelihood of the leak reappearing more regularly. - Run your program against
libgmalloc.dylibingdb. This library is an aggressive debugging malloc library that can help track down insidious bugs in your code. For more information, see thelibgmallocman page. - For Cocoa and iPhone applications, if you fix a leak and your program starts crashing, your code is probably trying to use an already-freed object or memory buffer. Set the
NSZombieEnabledenvironment variable toYESto find messages to already freed objects.
Most unit testing code executes the desired code paths and exits. Although this is perfectly normal for unit testing, it creates a problem for the leaks tool, which needs time to analyze the process memory space. To fix this problem, you should make sure your unit-testing code does not exit immediately upon completing its tests. You can do this by putting the process to sleep indefinitely instead of exiting normally.