How to get information about all memory allocated by an allocator?

Help
1

Im having an issue with uninitialized memory. I am making a trie and they all have a parent node. As far as I can tell, all memory should be initalized. But when I traverse the nodes backwards (from any node except root towards root) I get a

*main.Trie@aaaaaaaaaaaaaaaa, 򪪪, 12297829382473034410, false
General protection exception (no address available)
/home/segfault-enjoyer/hangman-solver/src/main.zig:162:27: 0x103cb9e in next (hangman-solver)
            while (current.parent) |parent| : (current = parent) {
                          ^
/home/segfault-enjoyer/hangman-solver/src/main.zig:65:23: 0x103df67 in main (hangman-solver)
    while (try it.next(allocator)) |word| {
                      ^
/home/segfault-enjoyer/.bin/lib/std/start.zig:524:37: 0x1039141 in posixCallMainAndExit (hangman-solver)
            const result = root.main() catch |err| {
                                    ^
/home/segfault-enjoyer/.bin/lib/std/start.zig:266:5: 0x1038c81 in _start (hangman-solver)
    asm volatile (switch (native_arch) {
    ^
???:?:?: 0x0 in ??? (???)
run

The Line above the general protection exception being the broken node.

Now I want to find out where this node has been allocated, is there a way to do this via the allocators api? Or is there some other idea of how to find the issue, I have never used a debugger before but id be willing to try gdb.

segfault-enjoyer/hangman-solver: Basically a follow-up to my older hangman-cheat. The goal is to play around with trees and tries - Codeberg.org This is the repository. WATCH OUT: theres an @breakpoint in there, dont be surprised if it just stops if its removed

1 Like
3

I think that this is what you are looking for, std.heap.loggingAllocator, from my experience this seems like you have pointers to the stack, and therefore in reverse the memory doesn’t mean anything anymore or maybe something along those lines, in anycase for the logging allocator, you just have to pass it your real allocator, and the logging allocator, will print when there is a memory allocation.

3 Likes
4

Yep I suspect something along those lines too, I just cant find the issue still. Thanks for pointing out loggingallocator, ill give that a shot

1 Like
5

I can try to look at it quickly see If I can find something

1 Like
6

Maybe your node_iterator is the problem I have to dig deeper.

EDIT I think I was right :

        /// Returns the backing array of values in this map. Modifying the map
        /// may invalidate this array. It is permitted to modify the values in
        /// this array.
        pub fn values(self: Self) []V {
            return self.entries.items(.value);
        }

Idk if you are modifying it again, but it seems like you shouldn’t really take a pointer to it ? This is from the Array hash map function

7

I suspect that to be the case too, addString is the only other contestant, but I really dont see an issue there, so node iterator is the next likely thing.

8

I’ve added the logging allocator, and reduced the number of entry to see things more clearly and when I run it I get this :slight_smile:

info: { A, A, I, I }
debug: free - len: 16
debug: alloc - success - len: 32, ptr_align: 2
*main.Trie@7f6694d261c0, G, 1, true
*main.Trie@7f6694cfe2c0, A, 11, false
*main.Trie@7fffb3bbbd90, A, 51, false
debug: shrink - success - 32 to 12, buf_align: 2
info: { A, A, G }
debug: free - len: 12
debug: alloc - success - len: 32, ptr_align: 2
*main.Trie@7f6694d261c0, F, 1, true
*main.Trie@7f6694cfe2c0, A, 11, false
*main.Trie@7fffb3bbbd90, A, 51, false
debug: shrink - success - 32 to 12, buf_align: 2
info: { A, A, F }
debug: free - len: 12
debug: alloc - success - len: 32, ptr_align: 2
*main.Trie@7f6694d24040, E, 1, true
*main.Trie@7f6694d261c0, E, 2, false
*main.Trie@7f6694cfe2c0, A, 11, false
*main.Trie@7fffb3bbbd90, A, 51, false
debug: shrink - success - 32 to 16, buf_align: 2
info: { A, A, E, E }
debug: free - len: 16
debug: alloc - success - len: 32, ptr_align: 2
*main.Trie@7f6694d24000, S, 1, true
*main.Trie@7f6694d089c0, A, 5, false
*main.Trie@aaaaaaaaaaaaaaaa, 򪪪, 12297829382473034410, false
General protection exception (no address available)
/home/pollivie/workspace/zig/hangman-solver/src/main.zig:164:27: 0x103da9e in next (hangman-solver)
            while (current.parent) |parent| : (current = parent) {
                          ^
/home/pollivie/workspace/zig/hangman-solver/src/main.zig:67:23: 0x103eea4 in main (hangman-solver)
    while (try it.next(allocator)) |word| {
                      ^
/home/pollivie/zig/0.14.0-dev.130+cb308ba3a/files/lib/std/start.zig:515:37: 0x103a081 in posixCallMainAndExit (hangman-solver)
            const result = root.main() catch |err| {
                                    ^
/home/pollivie/zig/0.14.0-dev.130+cb308ba3a/files/lib/std/start.zig:258:5: 0x1039bc1 in _start (hangman-solver)
    asm volatile (switch (native_arch) {
    ^
???:?:?: 0x0 in ??? (???)
9

This parts looks like debug memory initialization, so it does seems like the trie is pointing to memory that it shouldn’t

1 Like
10

Ou nice, I couldnt manage to reproduce with a simpler dataset

11

What I find very strange is how the three lines

*main.Trie@7f719e6d5c40, s, 1, true
*main.Trie@7f719e68fdc0, i, 1, false
*main.Trie@aaaaaaaaaaaaaaaa, 򪪪, 12297829382473034410, false

start with the end of a word, then continue to another one which is then broken.
Node iterator, however, only cares about the end of a word, so that makes me thing that the entire trie is broken. If node iterator would return a node, it would much more likely be
bad node -> garbage but it appears to be good node -> bad node -> garbage

12 
for (try self.stack.addManyAsSlice(vals.len), vals) |*s, *v|
    s.* = v;

in case you’re referring to this line, i dont think its the problem. I have also used a hashmap.iterator based approach before and the trie is never modified during iteration of its nodes / words

EDIT:

yep, the approach

var it = c.children.iterator();
while (it.next()) |e|
    try self.stack.append(e.value_ptr);

fails the exact same way

1 Like
13

If you want I have a Trie implementation in C, if you need to TRIE another Trie (sorry for the wordplay lol)

1 Like
14

hehe I couldnt have resisted either.

If it has iteration capabilities then yes

Speaking of, I could try to make a function that just recursively validates the entire trie, its not pretty but oh well, for debug purposes its okay

1 Like
15

@pierrelgol (if you dont wanna get pinged pls tell me, but i thought you may find this interesting)
Update: I have made some progress, i made my validate function report the amount of errors it found and correct them, it now runs which means that the error is in the trie and not the iterator logic. in ~450k words there were 147959 broken pointers lmao

This basically narrows things down to i think only addString

1 Like
16

No quite the opposite I’m a bit of a beginner, and so any findings is interesting to me, as it helps me grow too. So whenever you find exactly where that was coming from please hit me up.

1 Like
17

My hunch is that you’re running into a problem here:

    parent: ?*Trie = null,
    children: std.AutoArrayHashMapUnmanaged(u21, Trie) = .{},

by storing Trie as a value in the hash map and then storing pointers to those Trie values in parent, you are storing pointers to memory that is very likely to become invalid when the hash map resizes (since the memory for Trie values will be copied to the new location of the resized hash map data). You’ll likely want to change the children field to:

    children: std.AutoArrayHashMapUnmanaged(u21, *Trie) = .{},

and then allocate the Trie values on the heap so that pointers to them are stable (could use a MemoryPool for this).

2 Likes
18

Yep, thats it. @pierrelgol squeek and sze found the issue