Greg Price
Reputation: 2556
realloc, heap memory leaks
this is my count and say problem from leetcode solution. But with memory leaks https://leetcode.com/problems/count-and-say/
My makefile
build:
gcc main.c -Wall -g -o main; \
$(PWD)/main; \
My build commands
make
Or with valgrind:
make
valgrind --leak-check=yes ./main
Output: (correct, tested)
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
From Valgrind
==1796== Memcheck, a memory error detector
==1796== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et
al.
==1796== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright
info
==1796== Command: ./main
==1796==
==1796== Invalid read of size 1
==1796== at 0x100000930: countAndSay (main.c:62)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x10000096B: countAndSay (main.c:73)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x1000009D7: countAndSay (main.c:89)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 16
==1796== at 0x100655A65: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796== Address 0x10545d410 is 1 bytes after a block of size 4,463
alloc'd
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Conditional jump or move depends on uninitialised value(s)
==1796== at 0x100655A7D: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796==
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
==1796==
==1796== HEAP SUMMARY:
==1796== in use at exit: 29,301,895 bytes in 40,712 blocks
==1796== total heap usage: 80,412 allocs, 39,700 frees, 58,326,719
bytes allocated
==1796==
==1796== 72 bytes in 3 blocks are possibly lost in loss record 25 of 51
==1796== at 0x1000ABD72: calloc (vg_replace_malloc.c:755)
==1796== by 0x10075A7C2: map_images_nolock (in
/usr/lib/libobjc.A.dylib)
==1796== by 0x10076D4E0: map_images (in /usr/lib/libobjc.A.dylib)
==1796== by 0x100007C64: dyld::notifyBatchPartial(dyld_image_states,
bool, char const* (*)(dyld_image_states, unsigned int, dyld_image_info
const*), bool, bool) (in /usr/lib/dyld)
==1796== by 0x100007E39: dyld::registerObjCNotifiers(void (*)
(unsigned int, char const* const*, mach_header const* const*), void (*)
(char const*, mach_header const*), void (*)(char const*, mach_header
const*)) (in /usr/lib/dyld)
==1796== by 0x10022571D: _dyld_objc_notify_register (in /
/usr/lib/system/libdyld.dylib)
==1796== by 0x10075A073: _objc_init (in /usr/lib/libobjc.A.dylib)
==1796== by 0x1001AFB34: _os_object_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1001AFB1B: libdispatch_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1000BE9C2: libSystem_initializer (in
/usr/lib/libSystem.B.dylib)
==1796== by 0x100019AC5:
ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&)
(in /usr/lib/dyld)
==1796== by 0x100019CF5:
ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&) (in
/usr/lib/dyld)
==1796==
==1796== 168 bytes in 56 blocks are definitely lost in loss record 28
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 570 bytes in 1 blocks are possibly lost in loss record 37 of
51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 1,512 bytes in 378 blocks are definitely lost in loss record
38 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 4,462 bytes in 1 blocks are definitely lost in loss record 45
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000867: countAndSay (main.c:29)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 17,848 bytes in 1 blocks are definitely lost in loss record 46
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000857: countAndSay (main.c:28)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 19,257 (240 direct, 19,017 indirect) bytes in 1 blocks are d
definitely lost in loss record 48 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000839: countAndSay (main.c:19)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 61,644 bytes in 406 blocks are definitely lost in loss record
49 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 80,493 bytes in 379 blocks are definitely lost in loss record
50 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 29,093,648 bytes in 39,299 blocks are definitely lost in loss
record 51 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== LEAK SUMMARY:
==1796== definitely lost: 29,260,015 bytes in 40,521 blocks
==1796== indirectly lost: 19,017 bytes in 29 blocks
==1796== possibly lost: 642 bytes in 4 blocks
==1796== still reachable: 200 bytes in 6 blocks
==1796== suppressed: 22,021 bytes in 152 blocks
==1796== Reachable blocks (those to which a pointer was found) are not
shown.
==1796== To see them, rerun with: --leak-check=full --show-leak-
kinds=all
==1796==
==1796== For counts of detected and suppressed errors, rerun with: -v
==1796== Use --track-origins=yes to see where uninitialised values come
from
==1796== ERROR SUMMARY: 124 errors from 15 contexts (suppressed: 11
from 11)
main.c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SEQUENCE_COUNT 30
#define BUFFER_MAX 4462
char* countAndSay(int n) {
int msc;
if (n > 0 && n <= 30) {
msc = MAX_SEQUENCE_COUNT;
} else {
fprintf(stderr, "Error: The range for this count and say method is 1...30\n");
exit(1);
}
//Holds the array of sequences
char **out_buffer = malloc(msc * sizeof(char*));
//Holds current sequence
char *out;
int size = n;
//Holds previous sequence
char *prev_chunk = NULL;
//memory for the counts and says
int *counts = malloc(BUFFER_MAX*sizeof(int));
char *says = malloc(BUFFER_MAX*sizeof(char));
//index into the buffer memory of sequences
int index = 0;
//solve iteratively
while (size > 0) {
//base condition
//size counts down to 0, filling chunks, populating the next chunk to be processed
//filled chunks are placed in the out buffer at the index which is counting
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
//from 0 to index - 1 get the chunk to be processed, use it to put together
//the count and say chunk for adding to the index slot
for (int s = 0; s < index; s++) {
if (s == 0) {
prev_chunk = out_buffer[0];
} else {
prev_chunk = out_buffer[index];
}
//count the length of the current chunk
int length = 0;
for (int e = 0; e <= BUFFER_MAX; e++) {
if (prev_chunk[e]) {
length += 1;
} else {
break;
}
}
//The count of says at each iteration
int count = 0;
//say is a char byte from the previous chunk memory
char say = prev_chunk[0];
//skip is used in the iteration process
int skip = 0;
//The idx into memory for the counts and says
int idx = 0;
//iteratively generate the count and say chunk for this index
for (int i = 0; i < length; i++) {
if (skip > 0) {
if (i < length - 1) {
say = prev_chunk[i + 1];
}
skip -= 1;
continue;
}
if (prev_chunk[i] == say) {
count += 1;
counts[idx] = count;
says[idx] = say;
//if at the end of the iteration add one
//as a terminator for the counts, says, pairs
if (i == length - 1) {
idx += 1;
break;
}
} else {
count = 0;
if (i == length - 1) {
//finish off
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
say = says[idx];
idx += 1;
} else {
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
char next_say = prev_chunk[i + 1];
say = prev_chunk[i];
//Takes care of itself with idx
if (next_say != prev_chunk[i]) {
count = 0;
continue;
}
int y = i;
while (next_say == say && y < length -1) {
count += 1;
//dont need to up the index because we are counting howmany there are
says[idx] = say;
counts[idx] = count;
//skip because this is the next loop
skip += 1;
//subtract 1 because we want this to be in the final index slot
//count because we added an index
y += 1;
next_say = prev_chunk[y + 1];
}
idx += 1;
count = 0;
}
}
}
//Could have just generated the sequence from above but felt like doing this manually at the time
//If I get around to it ill change
int chunk_offset = 0;
char *temp = NULL;
for (int u = 0; u < idx; u++) {
int c = counts[u];
//TODO: factor out or use sprintf, or maybe not, maybe this is just faster
char cc;
if (c >= 10) {
cc = 'A' + c - 10;
} else {
cc = '0' + c;
}
char say = says[u];
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
out = realloc(out, chunk_offset + 3);
out = temp;
temp = NULL;
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
out = temp;
temp = NULL;
free(temp);
}
}
out_buffer[index] = out;
out = NULL;
free(out);
}
index += 1;
size -= 1;
}
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
}
int main(int argc, char **argv) {
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
}
I know it is not the best algorithm but it works. It is my understanding that realloc can be used in a way to avoid piling up malloc'd memory to the heap inside of loop's kinda like this which works. My suspicion is that by doing so it moves memory into places that are not easily found and free'd. Am I on the right path with that line of thinking? Simple realloc
char *e = NULL;
for (int i = 0; i < 10; i++) {
e = realloc(e, i + 1);
if (i == 9) {
e[i] = '\0';
} else {
e[i] = 'e';
}
}
printf("%s\n", e);
free(e);
Yields from valgrind:
==4421== LEAK SUMMARY:
==4421== definitely lost: 0 bytes in 0 blocks
==4421== indirectly lost: 0 bytes in 0 blocks
==4421== possibly lost: 72 bytes in 3 blocks
==4421== still reachable: 200 bytes in 6 blocks
==4421== suppressed: 22,021 bytes in 152 blocks
I have been running this with valgrind trying to pin down the leaking issue. I have also seen solution such as this and tried them with no luck: "Pointer being freed was not allocated." error after malloc, realloc.
I believe the main problem I am having here is that I malloc "out" the first time. After that I realloc it each time in the loop(s). Valgrind is giving the biggest leaks at line main.c:184 "out = realloc(out, chunk_offset + 2);". It seems like realloc is just deciding to put that memory somewhere in the heap and I cant get to it. I know the address can change from a realloc, but I still havent been able to get at it. How can I get definitely lost down to 0 in my countandsay.
Upvotes: 0
Views: 1247
Answers (3)
dbush
Reputation: 223739
Let's start with this block:
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
out = realloc(out, chunk_offset + 3);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
}
In both parts of the if, you expand the size of out, but then you immediately overwrite out with the value of temp, leaking the memory that out was pointing to.
Since temp contains the values you want, you no longer need what's in out, so get rid of the realloc on out and instead free what was there previously. Also, there's no need to free(temp) since it points to NULL, and you can replace the realloc calls with malloc since temp will always be NULL at that point:
if (u == idx - 1) {
temp = malloc(chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
} else {
temp = malloc(chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
}
free(out);
out = temp;
Then you have this at the bottom of your for loop:
for (int s = 0; s < index; s++) {
...
out_buffer[index] = out;
out = NULL;
free(out);
}
You overwrite the contents of out_buffer[index] on each iteration which leaks memory. You'll need to free the old contents first, and also get rid of the unneeded free(out) at the end since it contains NULL at that point. This also means you need to initialize out_buffer[index] to NULL before entering the loop.
out_buffer[index] = NULL;
for (int s = 0; s < index; s++) {
...
free(out_buffer[index]);
out_buffer[index] = out;
out = NULL;
}
Then you have an issue here:
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
Which fails to set out to NULL before the next iteration of the loop, which will result in out_buffer[0] getting free'ed and subsequently reading from free'ed memory. So add that here:
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
out = NULL;
continue;
}
Then at the end:
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
You don't want to free(prev_chunk); since it points to an old copy of out that was already free'ed. You're also not freeing out_buffer or any of the strings it points to. You don't want to free the string you return, of course, so skip that one:
char *rval = out_buffer[n - 1];
for (int i = 0; i < n - 1; i++) {
free(out_buffer[i]);
}
free(out_buffer);
free(counts);
free(says);
return rval;
Finally, make sure you free the result of this function once main is done with it:
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
free(cs);
Now you have a clean run through valgrind with no memory leaks or invalid read/write/free errors.
On a side note, there are a lot of inefficiencies in this code. On each iteration of the outer while loop, you generate the entire list from 1 to the current value of n. So on the first iteration you calculate n=1, then on the next you calculate n=1,2, then on the next you calculate n=1,2,3, etc.
You only need one loop here. That also means you don't have to reuse the current value of out_buffer but can instead just reference the previous one. I'll leave those changes as an exercise to the reader.
Upvotes: 2
Nominal Animal
Reputation: 39316
If we look at how the Look-and-Say algorithm works, we find that each character (or a sequence of same characters) produces a character pair in the output. Thus, if the length of the input is N characters, the length of the output is at most 2N characters.
Let's look at a function that generates the next string in the Look-and-Say sequence:
#include <stdlib.h>
#include <string.h>
char *look_and_say(const char *src)
{
const size_t srclen = (src) ? strlen(src) : 0;
char *dst;
if (srclen < 1) {
/* Nothing to look or say. */
return NULL;
}
/* The result can be up to twice as long as the source,
plus the string-terminating nul char. */
dst = malloc(2*srclen + 1);
if (!dst) {
/* Not enough memory for the result. */
return NULL;
}
{
const char *const end = src + srclen;
char *pos = dst;
while (src < end) {
const char *const was = src;
/* Skip repeated source characters. */
do {
src++;
} while (src < end && *src == *was);
/* The longest allowed sequence is 9. */
if ((size_t)(src - was) > 9) {
free(dst);
return NULL;
}
*(pos++) = '0' + (size_t)(src - was);
*(pos++) = *was;
}
*pos = '\0';
return dst;
}
}
The above does not care what the input string is; you can supply it anything. If the input string is NULL or empty, it will return NULL. If it cannot allocate memory (twice the length of the input string, plus one char for the string-terminating nul '\0' character), it returns NULL. If a character repeats more than 9 times in a row, the function returns NULL.
The Look-and-Say sequence is OEIS A005150 at the On-line Encyclopedia of Integer Sequences, which points out that R. G. Wilson v showed in 2004 that only digits 1, 2, and 3 exist in the sequence. Thus, for the integer sequence, the one could open-code the test whether a digit repeats (two or three times).
The length of each term in that sequence forms another integer sequence, OEIS A005341. It turns out that the length of term i is something like 1.56 × 1.304i (i.e, (size_t)(1.0 + 1.56*exp(0.26544*i)). The 30th term in the sequence is 4462 characters long.
If we wanted to generate each value in the sequence, we could use a single dynamically managed buffer (to hold the value being generated), and save a duplicate of each result:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
char *sdup(const char *src, const size_t len)
{
char *s;
s = malloc(len + 1);
if (!s) {
fprintf(stderr, "sdup(): Not enough memory for a duplicate of %zu-character string.\n", len);
return NULL;
}
memcpy(s, src, len);
s[len] = '\0';
return s;
}
/* Initial buffer size, at least 1. */
#ifndef INITIAL_BUFFER_SIZE
#define INITIAL_BUFFER_SIZE 1
#endif
char **look_and_say(const size_t count)
{
char **table;
char *src, *end;
char *dst, *pos;
size_t len, max = INITIAL_BUFFER_SIZE;
size_t i, k;
if (count < 1) {
fprintf(stderr, "look_and_say(): Count is less than 1.\n");
return NULL;
}
/* Allocate memory for the array of pointers. */
table = calloc(count + 2, sizeof *table);
if (!table) {
fprintf(stderr, "look_and_say(): Not enough memory for an array of %zu strings.\n", count);
return NULL;
}
/* First and last entries are NULLs; sentinels, if you will. */
table[0] = NULL;
table[count + 1] = NULL;
/* Allocate memory for the dynamic buffer. */
dst = malloc(max);
if (!dst) {
fprintf(stderr, "look_and_say(): Not enough memory for a %zu-character work buffer.\n", max);
free(table);
return NULL;
}
/* The sequence starts with "1". */
dst[0] = '1';
len = 1;
/* Save that. */
table[1] = sdup(dst, len);
/* Loop over the rest of the entries to be generated. */
for (i = 2; i <= count; i++) {
/* The source is the last item in the sequence. */
src = table[i - 1];
end = table[i - 1] + len;
/* Ensure we have enough room for the next value in the sequence. */
if (2*len > max) {
/* TODO: Better growth policy! */
max = 2*len;
pos = realloc(dst, max);
if (!pos) {
fprintf(stderr, "look_and_say(): Not enough memory to grow work buffer to %zu chars.\n", max);
free(dst);
for (k = 1; k < i; k++)
free(table[k]);
free(table);
return NULL;
}
dst = pos;
} else
pos = dst;
/* Source is [src, end[. pos is the next position in work buffer. */
while (src < end) {
const int nc = *(src++);
int nn = '1';
/* Skip if source is repeated twice or three times. */
if (*src == nc) {
src++;
nn++; /* 2 */
if (*src == nc) {
src++;
nn++; /* 3 */
}
}
*(pos++) = nn;
*(pos++) = nc;
}
/* Length of the generated value. */
len = (size_t)(pos - dst);
/* Save to table. */
table[i] = sdup(dst, len);
if (!table[i]) {
free(dst);
for (k = 1; k < i; k++)
free(table[i]);
free(table);
return NULL;
}
}
/* Dynamic buffer is no longer needed. */
free(dst);
return table;
}
#ifndef LIMIT
#define LIMIT 30
#endif
int main(void)
{
char **sequence;
size_t i;
sequence = look_and_say(LIMIT);
if (!sequence)
exit(EXIT_FAILURE);
for (i = 1; i <= LIMIT; i++)
printf("%zu. %s\n", i, sequence[i]);
for (i = 1; i <= LIMIT; i++)
free(sequence[i]);
free(sequence);
return EXIT_SUCCESS;
}
At this point, we must note that we already have an O(N) algorithm for generating the next value in the sequence, were N is the length of the previous value. Getting better than linear performance requires a better algorithm, but as far as I know, there is no trivial better-than-linear solution known for this.
We can optimize the above code at the code level, of course; but its time complexity is already quite good.
If we wanted to "cheat", we could observe that the lengths of the first thirty terms in the sequence are 1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904, 1182, 1540, 2012, 2606, 3410, 4462. This means that if we allocate enough memory for the pointers and 19019 characters (the sum of the lengths + 30 for the end-of-string characters), we only need a single allocation. If we reserve the zeroth pointer for a NULL, then that allocation would be malloc(19019 + 31 * sizeof (char *)).
However, continuing along that path, we end up with the following code, or something very similar:
static const char term_1[] = "1";
static const char term_2[] = "11";
static const char term_3[] = "21";
static const char term_4[] = "1211";
static const char term_5[] = "111221";
/* term_6[] through term_30[] omitted */
static const char *sequence[31] = {
NULL,
term_1, term_2, term_3, term_4, term_5,
term_6, term_7, term_8, term_9, term_10,
term_11, term_12, term_13, term_14, term_15,
term_16, term_17, term_18, term_19, term_20,
term_21, term_22, term_23, term_24, term_25,
term_26, term_27, term_28, term_29, term_30
};
This generates about 19 KiB of read-only (immutable) data in the generated binary. That would not be a problem even on many microcontrollers, if that sequence was somehow crucial for the operation.
If memory use is an issue, could trivially pack each individual digits in two bits, keeping access time reasonable, in which case only about 5 KiB of memory is used for the data.
Upvotes: 1
Ed Grimm
Reputation: 558
Your issue is that you are freeing the pointer you allocated at the end of the loop, even though you saved the pointer for posterity or something.
Based on this code, I'd say you want to do several things:
- Don't free memory you're not done with just because you're done with the variable that was holding onto its pointer.
- Change this to malloc rather than realloc, because you clearly are wanting a separate space for each pass through the loop.
- Get an editor that will help you with your indentation, or learn to configure the editor you use to help you with your indentation. This might sound like an opinion, but this looks like the sort of problem I've found is much easier to diagnose if your indentation means something. It'll probably also help you with getting help, because few expert programmers want to deal with inconsistent indentation like that. It's my impression I'm one of the few people who sees something like that and decides to pop it into vim, and then type
=ggto reformat everything to be reasonable. (Note: if you don't use vi, nvi, or vim, don't use it just because I do - all three of those editors have a huge learning curve, and most programming editors can do the same sort of thing.)
And just to reinforce the last point: Once I reformatted it to have consistent indentation, the problem jumped out at me. Tom almost got it, but I think he thought that was the end of your function, rather than the end of your loop.
Upvotes: 2
Related Questions
- Free all the memory allocated by malloc(), realloc() in C
- realloc, two dimention allocation, leak and errors in valgrind
- C problem with memory leaks (realloc function)
- Valgrind memory leak during realloc
- Valgrind crashes and gives me this invalid realloc warning
- malloc'ing and realloc'ing pointers causing memory leaks on return
- Realloc Using Way too much Memory
- valgrind report strange memory usage
- Realloc Causes Heap Corruption
- Valgrind reports memory leak for realloc call. But unable to understand why