How to implement reference counting in C?

read about it here .

I need to implement a variation of such an interface, let's say we are given a large memory space for management. There must be functions getmem (size) and free (pointer to block), which must be sure that they are free (a pointer to a lock) can actually free memory if and only if all processes using this block are executed using it .

What I was thinking about was defining the Collectable structure as a pointer to a block, its size and process using counting. then whenever a process using an instance of Collectable struct must explicitly increment the counter for the first time, and whenever the free() process has it, the count decreases.

The problem with this approach is that all processes must respond to this interface and do it explicitly: when assigning a collective pointer to an instance, the process should explicitly include this counter, which does not satisfy me, I thought, maybe there is a way to create a macro for Is this implicit in every assignment?

I am looking for ways to approach this problem for a while, so other approaches and ideas would be great ...

EDIT: the above approach does not satisfy me, not only because it does not look very good, but mainly because I cannot assume that the current process code will take care of updating my account. I need a way to make sure this is done without changing the process code ...

+6
source share
4 answers

An early problem with link counting is that it’s relatively easy to count the original link by putting the code in the malloc / free custom implementation, but it’s pretty difficult to determine if the first recipient passes this address to other users.

Since C does not have the ability to override the assignment operator (to count a new link), basically you have a limited number of options. The only one that can override the assignment is macrodef, since it has the ability to rewrite the assignment into something, which leads to an increase in the reference count.

So, you need to “expand” a macro that looks like

 a = b; 

in

 if (b is a pointer) { // this might be optional, if lookupReference does this work struct ref_record* ref_r = lookupReference(b); if (ref_r) { ref_r->count++; } else { // error } } a = b; 

The real trick would be to write a macro that can identify the purpose and paste the code without introducing other unwanted side effects. Since macrodef is not a complete language, you may run into problems when a match becomes impossible.

(jokes on how to see nails, where you learn how to use a hammer, have an interesting parallel here, except when you have only a hammer, you better learn how to make a nail).

Other parameters (perhaps more reasonable, perhaps not) are to keep track of all the address values ​​assigned by malloc, and then scan the program stack and heap for address matching. If you match, you could find a valid pointer, or you could find a string encoded with luck; however, if you do not agree, you can certainly release the address; provided that they do not store the address + offset calculated from the source address. (perhaps you can macrodef detect such offsets and add an offset as multiple addresses when scanning for the same block)

In the end, there will be no reliable solution without creating a help system where you pass back links (pretending addresses); hiding real addresses. The downside of this solution is that you have to use the library interface every time you want to deal with an address. This includes the “next” element in the array, etc. Not very C-like, but a pretty good approximation of what Java does with its links.

+3
source

Such a system in C requires some discipline on the part of the programmer, but ...

You need to think about property rights. Everything that contains links is owned and must track the objects to which they contain links, for example. through the lists. When an audit trail object is destroyed, it should loop its list of the mentioned objects and reduce their reference counters, and if zero kills them in turn.

Functions are also owners and must track the objects referenced, for example. by creating a list at the beginning of the function and scrolling it when returning.

So, you need to determine in which situations the objects should be transferred or shared by the new owners and transfer the corresponding situations to macros / functions that add or delete their objects to the lists of objects of the objects referenced by the objects (and adjust the control counter accordingly).

Finally, you need to sort out the circular links somehow, by checking for objects that are no longer available from objects / pointers on the stack. This can be done using the garbage labeling and garbage collection mechanism.

+2
source

Half-serious answer

 #include "Python.h" 

Python has an excellent reference count memory manager. If I had to do this truly in production code, rather than in homework, I would think about introducing a python object system into my C program, which would then make my scripting program a python script. See the Python C API documentation if you're interested!

+1
source

I do not think you can do this automatically without redefinable destructors / constructors. You can look at the HDF5 ref counter, but they require explicit calls in C:

http://www.hdfgroup.org/HDF5/doc/RM/RM_H5I.html

0
source

Source: https://habr.com/ru/post/915853/


All Articles