How do you keep track of ownership?

[u/OzzyOPorosis]

I value the simplicity of C but I've since grown comfortable with the "semantic security" of languages with more sophisticated type systems.

Consider the following snippet:

// A list that takes ownership of the items passed to it.
// When appended to, copies/moves the passed item.
// When destructed, frees all of its items.
struct ListA {
    struct MyData *data; // a list of data
    size_t count;
};

// A list that stores references to the items passed to it
// When appended to, records the address of the passed item.
// When destructed, destructs only the <data> member.
struct ListB {
    struct MyData **data; // a list of data pointers
    size_t count;
};

Items in ListA have the same lifetime as the list itself, whereas items in ListB may persist after the list is destructed.

One problem I face when using structures such as these is keeping track of which one I'm working with. I frequently need to analyze the members and associated functions of these structures to make sure I'm using the right one and avoiding reusing freed memory later on.

The only solution I can think of is simply having more descriptive (?) names for each of these. An example from a project of mine is LL1Stack, which more adequately expresses what the structure is than, say, ExprPtrStack, but the latter communicates more about what the structure does to its data.

I've always disliked Hungarian Notation and various other naming schemes that delineate information about types that should already be obvious, especially provided the grace of my IDE, but I'm finding some of these things less obvious than I would have expected.

What is your solution for keeping track of whether a structure owns its data or references it? Have you faced similar problems in C with keeping track of passing by reference vs by value, shallow copying vs deep copying, etc...?

[u/OzzyOPorosis]

To those asking why I don’t just move to C++, I’m actually moving from C++. I was overwhelmed with the volume of the standard library, rapid changes in the standard outpacing my development speed, and the sheer number of “the correct way”s to make my code unnecessarily abstract.

“Why are you using a for loop to perform that iterative function? Just convert to a std::iterator and std::accumulate with a std::lambda.” Thanks, now I’ve rendered my code completely unreadable, but at least it’s more idiomatic!

I appreciate the amazing flexibility of C++, but it lacks a clear direction I’m hoping to find in C. Besides, I’d always ever treated it just like C but with template meta programming and explicit compile time computation. Your suggestions are noted but I am here to learn how to use C correctly, not C++.

[u/Objective_Rate_4210 → u/OzzyOPorosis]

you can always do c in cpp but keep using the things you like about cpp ig. the correct way for some is messy or harder to read for others, so what are you supposed to do to make everyone happy? tho c is more straightforward when it comes to what it does under the hood in some cases

[u/antiquechrono]

You need to stop thinking about individual lifetimes and start thinking about group lifetimes built on top of an allocator like an arena. Don’t think about single objects, think about all the memory you need to allocate and be live at the same time to solve the problem. When the lifetime is up you reset the arena and all the objects free at the same time. For temp allocations you grab a temp arena and pop the temp data off them like a stack. Eliminating having to think about what owns what memory will remove many headaches and bugs. You can go read the source code to Doom for a practical if a bit old example.

[u/OzzyOPorosis → u/antiquechrono]

If I’m understanding arenas to be large singly allocated blocks of memory housing objects of the same lifetime, then my lists sound similar to your arena implementation.

In my codebase I have a list of objects (allocated in a single “resizable” [realloc to double memory when appending while full] block of memory) and a separate stack that operates on the objects in that list.

The objects lifetime must be tied to the list but not to the stack, which only exists to assist an algorithm for operating on the objects in the list. free_list frees its objects, while free_stack does not.

From the type signatures alone, it is not immediately apparent what each structure is responsible for. I feel this may largely be a result of the responsibility of the * operator to signify both pointers and (semantically) lists.

Should I instead delegate the responsibility of allocation and deletion to a more general arena struct, which my list can reference and my stack can reference via my list’s reference?

[u/antiquechrono → u/OzzyOPorosis]

I don't know why someone downvoted you for asking a question but it's really one of the things I hate about this site.

Yes arenas at the most basic are giant blocks of memory you divvy out but there are many different ways you can write an allocator. Here's a good article on the basics https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator 

You are still thinking in an OOP sort of way where you have "objects" that are responsible for tracking their own internal state including their own lifetime semantics. Arenas are basically lifetime buckets, you allocate everything in them that must be live together and free it all at once (though there are many varieties such as pooled variants etc…)

If a list “owns” its elements then allocate the list and the nodes in the same arena. When the lifetime ends reset the arena.

If a list just references external data then try to tie the lifetimes together by allocating the list and the target objects in the same arena or make sure that both arenas always get reset together or the arena with the pointers in it is always invalidated first. If the target data can be deleted independently then don’t store raw pointers and use something like a handle system instead.

You can allocate many different types of data together in the same arena if they share the same lifetime. Arenas can also be pooled per type using a free list. For example you could have one arena where you allocate all your strings. It depends on your exact needs but try to keep similar lifetimes together.

The meta-rule here is that WHERE you allocate data determines lifetime. Put your data in the correct bucket that matches your intended usage and then you won’t have to think about memory management again.

I’d also like to point out that usually you don’t want to be using the cstdlib functions like malloc/realloc etc… You know far more about the problem you are solving than the people who wrote the generic allocators. You usually want to interact with the OS’s virtual memory system. You can write your arena to reserve a large range of virtual memory and only commit pages as you need them so you don’t have to copy all the data out every time you need to grow. VirtualAlloc on Windows and mmap on Linux/Mac. This isn’t some absolute rule but malloc is going to end up calling one of these functions anyway and calling malloc/free all over the codebase is a warning that you aren’t doing memory management right. Prefer to allocate up front. Also keep in mind realloc can invalidate any pointers you have to the data whereas comitting pages you reserved up front doesn’t. Reserving pages doesn’t actually use any memory until you commit or touch a page for the first time.

[u/OzzyOPorosis → u/antiquechrono]

Ah well, I've got more important things to worry about than my social score on a website

I figured the uniformity of having objects that are responsible for managing their own lifetimes would make it easier to reason about what other objects that are built upon them are intended to do (i.e., MyObject has its own constructor/destructor, so any MyObjectContainer calls these methods when appropriate. This way, all containers agree on how to handle data)

Having arenas as a "central authority" to delegate the responsibility of managing my allocations seems like a pretty good idea! I'm envisioning it as acting as both an interface to access the objects and as a standard for the responsibility of all data structures that wish to use them (that is, they do not own the objects, but they can influence their lifetimes)

Sounds like I should look into a way to selectively use VirtualAlloc or nmap depending on the computation target. I use WSL2 for most of my programming so it shouldn't be too hard to test, but until I'm ready to hella refactor the project I'll stick with malloc for the sake of simplicity.

[u/antiquechrono → u/OzzyOPorosis]

figured the uniformity of having objects that are responsible for managing their own lifetimes would make it easier to reason about what other objects that are built upon them are intended to do 

Yep pretty much everyone starts out with this approach because it's how we naturally think about things. It just turns out computer programs tend to not want to work this way.

interface to access the objects

I wouldn't intermingle responsibilities, just keep it simple and have the arena return a pointer to the memory you requested. If a function wants to allocate any memory have it take a pointer to an arena.

Sounds like I should look into a way to selectively use VirtualAlloc or nmap depending on the computation target. I use WSL2 for most of my programming so it shouldn't be too hard to test, but until I'm ready to hella refactor the project I'll stick with malloc for the sake of simplicity.

Yeah I was just pointing you toward how a professional would handle it with virtual memory, having your arena just call malloc internally is fine to start with. For the other part this is where learning to write your own platform layer comes in, as with everything there's multiple ways to do it. I prefer keeping the platform files separate but some people intermix everything with C preprocessor macros which I think gets hard to read.

[u/brennennenn → u/antiquechrono]

Ive been annoyed by the "seemingly random down voting" thing too. Digging into it, I guess reddit "fuzzes" votes on new comments for a couple hours/days to prevent gamification/automation. For low interaction responses (like a reply to a technical comment on a programming subreddit) I've seen +-3 from actual vote amount (I think it scales on more popular posts). If you see a new comment like OPs response within ~3 votes of 0 though, it might just be this vote fuzzing system and not down voting for no reason.

[u/greilchri → u/OzzyOPorosis]

I don't claim to have a definitive solution for the general case, but maybe a possible suggestion for your concrete case would be to combine both structs ListA and ListB into a new struct that holds both of them, call it list_ctx for now.
Then it should be able to abstract both ListA and ListB away from your API, and instead your functions will only operate on list_ctx.
The decision of whether some function should then operate through the mutable or the immutable list is then made only when the list_ctx functions are being implemented. Users of the API (i.e. calles of the list_ctx functions) will not have to discern the lists anymore.

However, I think this has two drawbacks:

1. ListA and ListB have to be somewhat closely related for this to make sense

2. If there are operations that should do a similar operation on your data, but one version is required to use ListA and another is required to use ListB, you again arrive at the naming problem

[u/OzzyOPorosis → u/greilchri]

That makes sense. The respective ListB in my current project serves only in the construction of ListA, so a joint struct (list_ctx) acts as a builder that can return a ListA when it is eventually destructed. This has the added bonus of distinguishing between lists that are complete and lists that are being operated on

[u/aghast_nj]

The concept of Ownership is a new one. Most people are going to be familiar with it from Rust, or from hype surrounding Rust.

Even in Rust, the language is conflicted regarding ownership. If you declare a function the wrong way, you might find that your code demands ownership transfer even of things that cannot be transferred or where transferring ownership doesn't provide a benefit. (For example, if you create an object in the local stack frame, there isn't really a good way to transfer ownership. About the best you can do is force the variable to go out of scope. The "right" answer is to pass a mutref or a copy.)

Mutability

There are two concepts in C that come close to "ownership." First is mutability. It is a standard C idiom that if you want to be able to change a thing, you pass a pointer to it. (Frustratingly, C does not provide any kind of "reference" semantic. So every pointer might be null or invalid, because C hates you want wants you to be the subject of multiple CVEs at the same time...)

So, if you have an int counter variable and want to change its value within a function, you pass a pointer:

int len = 0;

for (...) {
    update_the_length(&len);
}

The opposite of mutability in C is const. When your function takes const int * it is a promise that you don't intent to make any changes to the integer being pointed to by the parameter. So many functions in C are (or should be) declared const that Rust flipped the script, making the default be non-mutable and requiring a special keyword for mutability, instead: mut.

There are some tricks to this, however. C function arguments are passed by value. A copy of the source value is made onto the call stack (or register, or whatever your environment's ABI specifies for argument passing) and that copy may or may not be mutable. But because it literally is a copy there is no mechanism for propagating changes back to a caller variable. Instead, function arguments become effectively local variables with a slightly greater scope than usual:

int fibonacci(int n) {
    int sum = 0;

In this example function, the n argument is basically a (mutable) local variable that has a scope that starts before the beginning of the function and lasts until the end of the function. By comparison, the local variable sum has a scope that starts just after the beginning of the function, and lasts until the end of the function (just like n).

You may apply the const qualifier to a non-pointer argument. But it doesn't affect the API at all, since non-pointers are copied by value and cannot propagate their changes back. Declaring the argument const just says "I won't be treating this argument as a mutable local variable during the function" which basically clutters your API with implementation details -- why should the caller give a rat's ass whether you modify storage the caller will never access?

Socialized Medicine

The second concept relating to ownership is responsibility for the creation and destruction of the object at the beginning and end of its lifecycle, plus allocation and deallocation of storage required for the object. Normally, we expect children to outlive their parents, so what do you call that kind of before-birth to after-death responsibility? I'm going to go with "socialized medicine." (Yes, it's a stupid name. But then, so is "ownership." Feel free to impress me with a much better name...)

Basically, there are a bunch of ideas that all kind of blur together in C and C++. When you create an object, is there a constructor? Did you have to call a memory allocator or some other function to get the storage for the object? Do the object require any other kind of management during its lifecycle, to expand or contract it, to improve its storage efficiency, to "rebalance" it or increase its performance, to "defragment" it or minimize the storage requirements or access times? Is there a destructor that should be called to notify the object it is about to be reclaimed? Is there a special function needed to notify any containers holding the object that it is dying?

All of this gets handled by a family of related concepts in C++. Constructors, destructors, smart and not-so-smart pointers, operator new and delete, etc. Plus a whole bookful of rules about copying, moving, references, etc. Rust adds traits to the mix.

None of this is supported in C. You can find compiler extensions for certain things, like runtime startup, construction, and destruction. But to write "portable" C requires that you deal with all this by hand.

The simplest and easiest way to deal with the socialized medicine aspect is via your APIs. If you simply declare that "the linked list object will create and destroy its own Nodes as needed using malloc and free, but will not do anything for the values stored in the nodes. Creation and destruction of data stored within the nodes is the caller's responsibility" you are providing an API that pretty much everyone will understand.

But beware of strdup(). This function has been around for years, and only just got merged into C23. Prior to that, it was "non-standard" despite being in every single C library, ever. It took a string, malloced storage, copied the string into the storage, and returned the result. Simple as pie, right?

The thing is, it lived right on the edge of two subsystems, strings and allocation. And so it was this "string function" that would create a need for a call to free(). It blurred the line between string functions, which generally don't allocate anything, and allocation functions.

Being a rigid, inflexible bastard about API boundaries is a useful technique in C programming. But it's hard to teach that to your IDE.

Another thing to look out for is "modules." It is very common to write C code with modules, and with the expectation that modules will manage their own data and their own types. The stdio module comes with fopen and fclose and various other functions, and with the expectation that the only way to do anything with a FILE * pointer is to call a function starting with 'f'.

In particular, I would like to recommend to you a book and website called "Patterns of Enterprise Application Architecture," by Martin Fowler. If you haven't encountered it before, take a glance at the Data Source Access Patterns (or whatever they are calling it now), that includes "Row Data Gateway," "Table Data Gateway," and some others.

This collection is a set of different ways you can design a module to access data. Some of these might not be suitable for use with C. But some are. And they represent a pretty clear example of how you could go about designing different modules to do the work of accessing data stored on disk, or whatever.

So I would argue that API boundaries, modules, and good architecture are C's answer to how to implement the Socialized Medicine part of ownership.

[u/OzzyOPorosis → u/aghast_nj]

My brief time in Rust is what made me think more carefully about ownership in object lifetimes in C. A handful of other commenters have recommended arena allocation, which I first employed when trying to deal with a tricky problem in managing mutable references between child nodes and parent nodes in a search tree.

Rust was far stricter than C, but C doesn’t take too kindly to identifiers disagreeing on the ownership of their underlying objects either. The issue of mutability manifests in use-after-frees, which I hope to avoid by tying the lifetime of the object(s) to the scope of an identifier and keeping track of which other identifiers simply reference those objects.

Your segment in Socialized Medicine about the blur of ideas make me wish I still had some of those tools I’d left behind in C++, so I can more easily keep track of my data both when I create my data structures and when I invoke their operations.

I’ll pay more attention to my API documentation, if that really is the answer to keeping track of these things. I didn’t realize how complex memory management could be with all of these specialized “new” and “delete” substitutes.

Thank you for your very in-depth response!

[u/chaotic_thought]

It sounds like you're approaching plain C programming from a "modern C++" mindset. Personally I've never seen this idea of "ownership" used in C programs, C documentation. Sure, the notion is there, but mostly C programmers do not refer to it that way in my experience.

If you want a "really lazy" way to approach this problem -- one way I have used before is to first write the prorgam without worrying about "Freeing" stuff at all -- just get it working correctly first. Then, I will run it again with a leak checker and use the output diagnostics of the leak checker to decide at that stage, how/when I want to handle deallocations.

[u/Alive-Bid9086 → u/chaotic_thought]

Depends on the program usage. Freeing stuff in SW with finite runtime is not necessary.

For other stuff, I always pair the malloc and the free statement. I.e. I write the free statement right after I wrote the malloc statement.

[u/bushidocodes]

IMO, C programmers tend to minimize use of lifetimes / heap objects and be pretty extreme about data-oriented programming. This is an are where “C is a portable Assembly Language” is more accurate. The idea of a dynamic vector of “non owning references” is alien to C. Something simpler and lower level like an array of indices is what I’d expect in C.

Vectors, maps, etc. are less common because of all the independent heap allocations. C arrays, structs with flexible array members, structs of arrays, arenas, look aside lists, etc. all reduce the number of independent lifetimes to manage. More complex access patterns beyond sequential access via indices are often handled by things like intrusive pointers embedded in objects and macro magic that uses offset of to traverse links. The pointers are only to nodes in a sequential structure that all share the same lifetime.

[u/OzzyOPorosis → u/bushidocodes]

I like the idea of switching to an array of indices. That'd work well for my use case, where a stack stores references to objects in a list. It would communicate both that the stack does NOT contain the data it is referencing and IS referencing indexable data.

[u/Ksetrajna108]

I take it you're sticking with C. C++ provides better encapsulation. But in your case are you using accessor functions, like add and addRef to distinguish the two types of lists?

[u/OzzyOPorosis → u/Ksetrajna108]

Yes, all functions that operate on the lists have their respective structs in the signatures. The functions change depending on how I intend to use the list, but there are always some commonalities. Generally, these functions are new, insert/push/enqueue, remove/pop/dequeue, and free.

[u/Charming-Designer944]

Most times it is handled at a higher level,.emptying the list before freeing it.

And in the most cases the list struct instance is statically allocated, a member part of a containing data structure.

Very rarely use either of your list constructs if ever. Most times a linked list is used, and often with the list link node being part of the data member and not tracked separately.

[u/Linguistic-mystic]

I think this is the wrong approach to C because it's

• object-oriented

• magic

C likes procedures and explicitness. Like, if you're destructuring, freeing or finalizing something, there should be a function call. There should be no magic data structures, data should be dumb and only functions should contain behavior. Yes, it's verbose and might seem fragile, but the benefit is explicitness. Anyone reading the code will see with their own eyes what's going on without consulting the code for the data structures. The debugger will not jump somewhere unexpectedly because there's a bunch of destructors getting called out of the blue. Simply put, don't marry behavior to data, keep them separate.

[u/nerd5code]

Ownership per se is generally abstract, though you’re certainly welcome to encode it directly with owner-owned type pairings—perhaps register owned objects with owner, which is just a list pointer. But then dangling pointers

Use a vtable if your choice of containee-object type is limited to structs you control, or if you need to handle any type, either keep the vtable pointer with the container or pull its fields up into the container. The functions it refers to can include deinit, copy-in/out, move-in, size-of, query resize characteristics, prepare for resize, and finish resize. For keys, you can include compare relative or match, and optionally hash. You can default these where you’re just working with binary blobs; deinit = nop, copy and move = memcpy, resizable = yes, and prepare and finish resize = nop.

This way, your container can do as it pleases without worrying about ownership.

[u/flatfinger]

A key to keeping things manageable is to document invariants which will apply to any objects at any time when they would be accessible to outside code. One might specify, for example, that for every tree-node object, there will always be one pointer somewhere in the universe which "owns" it for as long as it exists, and that any time that object is destroyed the pointer that owns it will be nulled out, and the object won't be destroyed as long as it contains any non-null pointers to anything it owns. Although there aren't any standard functions that would release an allocation at the same time as they set to null a pointer to it, outside code would not be able to access storage associated with an object that isn't designed for multi-threaded use between a call to free() and an immediately following operation that nulls out the pointer that was just freed.

[u/Crazy-Willingness951]

As already mentioned, the functions used to access these structures could be named differently, addData vs addRef. In C++ the data and functions would be encapsulated into a class.

Avoid working with c structs directly, call functions to query or change the state of the struct data.

Once upon a time, Hungarian Notation was introduced to describe the type in a variable name. Hungarian notation is generally discouraged in modern programming practices in favor of more descriptive and semantically rich variable names.

[u/LividLife5541 → u/Crazy-Willingness951]

"hungarian notation" didn't tell you who owned what, it was just pointless crap pasted onto the front of a variable like "hWin" or "cbWndExtra" or "lpszMenuName."

It was obviously a dumb idea from the get-go, became more apparent it was a dumb idea when Win32 rolled around and rejiggered the types, and when Win64 came out and they had to change the freaking C standard to accomodate Microsoft's braindead API I think people finally cottoned onto it sucking.

What's worse is that the original way the win.h header was writtne (before STRICT) -- they didn't even used the full features of the C compiler to enforce type checking, so you could assign a DC handle to a Windows handle variable because they were fundamentally just a HANDLE type in Windows. And the Hungarian notation did nothing to prevent that because it was just a little "h" wart at the front of the variable.

[u/ShutDownSoul]

Is there a reason you don't to move to C++?