Þ   briarpig  » code  » pool

     This page shows C-based memory allocation in two flavors: 1) reference counted and 2) iovec pools. Class names used are short and somewhat arbitrary (verging on weird). Refcount support here is a C rewrite of C++ in the node thorn demo, using hand-rolled vtables for virtual methods.

     The purpose of cy_pool is to abstract heap allocation so C++ classes (like Vt in the vector template) can use C-based memory pools, even when storage is statically allocated.

     The purpose of cy_vat and vat subclasses is to provide a standard factory source of refcounted objects, using api that can be defined and used in C. Vats allow C clients to define refcounted objects that can be passed in and of subsystems written in C++.

     The purpose of cy_fix is to represent a refcounted node that can be fixed (pinned) in place with a ref. The purpose of cy_gum is to securely hold such a reference, so refcounting can be done by managing a population of gum instances.

     Ultimately, a specific short term purpose of cy_vat, cy_fix, and cy_gum is to support cy::Row on the row page, which clones the deck implementation, replacing std::vector with cy::Vt on the vector page. Since the cy_pool api supports memory allocation by cy::Vt, all the clases on this page support row directly or indirectly in C-based scatter/gather utilities in C++.

     Terms vat and pool mean nothing more than heap; both are just sources of allocated memory. A subclass of cy_pool is little more than a heap with alloc and free methods. But a subclass of cy_vat allocates refcounted subclasses of cy_fix (the same thing as a yn node in the node demo) which are anchored in place by cy_gum handles (the same as yh thorn handles).

     Terms fix and gum emphasize a desire to pin a refcounted object in place as long as you hold a reference. The cy_fix subclass allows you to fix (pin) an instance in place while you hold a reference. By design, cy_gum instances fix a reference in place for you, so gum is what makes a fixed object stay in place. (Fix and gum were simply the shortest words in a thesaurus that meant close to the right idea.)

     Base classes cy_fix and cy_gum are defined in C because actual storage management may be defined in a C runtime. But subclasses can be written in C++. Examples of this appear below.

     In particular cy::GumT is a preferred subclass of cy_gum to use in C++. It's a template you can specialize to a subclass of cy_fix for typesafety. Basically cy::GumT is a smart reference like auto pointers in other libraries; it's a clone of template yht handles in the node thorn demo.

     Clones of struct iovec abound in cy source code. Here's one more. All cy iovecs are considered physically equivalent to the extent you can safely cast, blindly, from one to another.

     The cy_viov object below represents a vector of iovecs as a single value.

     The following C api is a clone of yn in the node thorn demo, but with a few methods removed. The pin and unpin methods mean add a reference and remove a reference. To support copy-on-write, the refs method returns the current refcount. (Note: this is only safe in single threaded systems.) The cite and dump methods provide single and multi-line print formats, allowing all refcounted objects to be printe, and by extention all gum handles pointing to a fix refcounted subclass.

     The term fix emphasizes your ability to pin an instance in place by adding a new counted reference. Under thorn, the term node emphasizes a role as one node in a graph. Here the term fix treats ability to fix in place as more important than being a node in a graph. The name announces: you can fix this in place with a gum handle, describing an aspect of how it's used.

fix vtable «

     Each cy_fix subclass defines methods with signatures exactly matching those above. Then a vtable with the following format is created—only one global instance is needed because all instances of the same fix subclass can share the same vtable pointer.

     Each cy_fix subclass starts with the following fields, beginning with the vtable pointer. The tag field must contain octet 'F' as a magic signature for dynamic typing. But the type field can vary on a per subclass basis. Neither fix_gen nor fix_type can change during the lifetime of one fix instance.

     Presumably refs to fix subclasses are stored in cy_gum instances shown below. Each gum instance copies both the fix_gen and fix_type fields, then later asserts those values have not changed. This catches refcount errors by asserting object lifetime and format does not change as long as refs are nonzero.

fix base «

     The following two methods are preferred ways to get pseudo random starting generation numbers to put into objects like cy_fix

     Inline methods below merely call the virtual methods by dispatching through the vtable. (When the vtable is wrong, one should hope you crash.)

fix dispatch «

fix cow «

     The following nice methods query whether a fix instance should copy itself (copy-on-write) to be nice to other users sharing state with this instance. As a mnemonic, thing of nice as node+ice: a frozen node because it has too many refs. (See the node thorn demo for more comments on copy-on-write).

generation numbers «

     The best way to initialize fix_gen in each fix instance is by calling cy_rand_gen16() below.

gum handles «

     A gum instance is a small handle holding a ref to a refcounted fix instance. This clones yh0 handles in the node thorn demo.

     The central method is cy_gum_set(), which sets the gum_fix while managing all the details of releasing any old reference, and copying values from each fix instance into gum_gen and gum_type to detect errors.

gum-constructor «

     You construct an instance using constructor cy_gum_ctor() below (or by using subclass cy::GumT in C++).

gum references «

     This set() method is a clone of yh0::_hsetn() in the node thorn demo (cf «). This is the primary way in which fix instances should be refcounted in code using cy api. The intended invariant is easy to say: a fix instance remains alive if and only if a reference from a gum instance still exists. The refcount of a fix should exactly equal the number of gum instances pointing to that refcounted fix object.

     (If you decide to refcount another way—say by manually calling the pin and unpin methods—you have my sympathies: I've never seen it done correctly without refcount leaks or double releases. Avoiding that expected normative failure is exactly the reason I designed this sort of fix and gum api.)

gum dereference «

     This fix() method is just a getter returning the gum_fix pointer, but for use in any context where a nil pointer is considered a disaster. For example, when a cy::GumT smart reference uses the pointer in operator->() or operator*(), which both dereference the pointer, it helps to log debug info to a log.

gum wellness «

     A gum instance is considered good (well-formed) when it contains a nil pointer, or when the fix pointer points to a fix instance whose current generation number and type match those held inside the gum instance. You can use calls to cy_gum_good() for assertions that references are still good, since otherwise you might not see a problem until the reference is released later (possibly a long time after a problem began).

gum printing «

     A dump method allows multi-line format when necessary (unlike cite format aiming for one line only). When you print a gum handle, it also prints the fix instance inside when one is present. Basically, each gum is considered a proxy for the fix value inside.

     By convention, the arc parameter is the name of the field whose value is this gum handle. If data structures are object graphs, then each fix is a node and each gum is an arc pointing at that node (which explains node and handle terms in thorn).

     Template class GumT below is a subclass of C-based cy_gum which adds support for smart reference and smart pointer semantics, as well as RAII (resource acquisition is initialization) support. The first GumQ struct shown acts as the wrapper GumT uses for printing control.

     Sometimes it is useful to declare typedefs like FixGum below instead of writing GumT<cy_fix> (which looks horrific as a value in other template classes like Vt<E> on the vector page).

     The following GumT<F> template class should be specialized with a cy_fix subtype. For example, cy_fix itself is fine to use as F; or you might use IovFixEtc when only that subclass will be held by a gum instance.

     This template code clones the yht handle subclass shown in the node thorn demo (cf «).

     The purpose of this abstract vat api is to provide a standard factory for refcounted fix subclass allocation. Each vat is a container of fix instances. The api implies nothing about whether any given vat can be used for all fix subclasses, or just one. This issue is your problem to manage.

     This api is C-based because memory heaps might be implemented in C, and yet code in C++ might want to use this api anyway. The result is ugly for C++ code, but allows any C client to provide correct memory service.

     Returned values come in two flavors: iovec and gum handle. When you are most interested in the iovec itself, you can treat the gum as secondary. But when raw space in iovec form is not useful, the gum is primary (and you will need to cast the cy_fix* pointer to MySubclass*.) To free the fix instance later when refs hit zero (and only when refs hit zero), you only need the cy_fix* pointer. Presumably the unpin() method of the fix instance sees refs hit zero and then passes this pointer back to the vat in a virtual call to vat_free_do().

vat vtable «

     Each vat must support three allocation methods and one free method. The alloc method resembles malloc(), except the object pointer returned in the gum parameter must be a subclass of cy_fix. The iovec returned specifies the address of usable space in iov_base and the length of that space in iov_len. The cy_fix itself, as a whole, is not described by the iovec unless there's no separate space inside the cy_fix subclass to use as raw space.

     By definition, the refcount of the cy_fix returned is expected to be one, because the first reference should have gone into the gum provided. However, you might be able to make a vat that re-shares existing fix instances when this makes sense, somehow. (If so, you must only use that vat when callers know the behavior is a bit weird.)

     The copy method is logically the same as alloc followed by a copy from the source to the new object. This basically aims to reduce tedium in callers who would otherwise perform copies at calling sites.

     The free method is exactly what it seems: the moral equivalent of free() to match the malloc() of the alloc method. The refcount in the fix instance must be zero, and the free method should assert this. Whether space is actually returned to the heap or to some free list is up to the vat.

     The bind method has a long explanation if I go into every detail, so I won't. Instead I expect you to fill in blanks after a few clues. But basically it deals with scatter/gather allocation. It's an N-way version of the alloc method. This is necessary when a vat's free pool of space has a maximum size granularity, and you ask for more space than this in one request.

     Consider two extemes any vat subclass might pursue. First, if arbitrary size allocations are supported, bind can do exactly the same thing as alloc, returning output using only the first slot in both the iovec and gum arrays. But there's another possibility: Second, if a vat has a pool of single-sized buffer—two or four kilobytes apiece for example—then a single large allocation might require a sequence of smaller discontiguous pieces. For example, a 32K request migth be filled with sixteen 2K buffers, if the arrays of iovecs and gums have length of at least sixteen. (The purpose of vat_max, when the value is not zero, is to reveal the maximum size of an allocation that bind will do in scatter/gather style, so a caller can correctly know length of arrays necessary.)

     You might ask: why not just use alloc N times instead?

     Because that can cause deadlock: two flows of control, both trying to get N buffers, might exhaust available space without either getting enough to finish a task so space can be released. So the real purpose of bind is to allocate all the space at once, or not at all, to avoid deadlock. Are you having fun yet?

     Note the heap-based subclass shown below on this page does the simple case: a single contiguous allocation. And the current row implementation uses alloc instead of bind like it should. There's one of the loose ends I said I would not tell you about. I must have had a surge of sympathy for your viewpoint. Code here does not use the ability of bind yet, though it's important in this api.

vat constructor «

     The constructor initializes ever field. As you look at this abstract object, then compare to others on this page, you might notice some objects put methods in a separate vtable (cy_fix for example) while others like cy_vat put the virtual methods in the object itself. Why is that? Why use separate vtables? Why not here?

     It's all a matter of how many instances are expected. I expect a huge number of fix subclass instances, but very few vat subclass instances. Thus space efficiency matters in cy_fix but not in cy_vat, so only the former factors out virtual methods in a separate object. That's the whole reason. If I ever needed a zillion vat instances, I'll change cy_vat to look like cy_fix.

vat dispatch «

     Innline methods are a standard way to call virtual methods:

heap vat «

     The following vat subclass uses malloc() and free() for allocation. Since the heap is used for space, this subclass is named cy_heapvat. These four methods go into the vat vtable:

     An instance of cy_vat is declared first to make cy_heapvat a subclass in the sense a pointer to one is a pointer to the other. (A subclass written in C++ can simply use normal inheritance notation, but cy_heapvat is a subclass written in C.)

     All the other fields are just counters for usage statistics. They aren't necessary, but in practice you are going to wonder whether actual usage matches what you expected. Note absence of any mutex support—this implies cy_heapvat is single threaded in expected use. (But it need not be since malloc() and free() are thread safe.)

heap vat constructor «

     The constructor simply construsts the base vat class first, then zeroes all counters.

heap vat global «

     Since this heap vat uses the global heap to allocate and free, there's little reason to have more than one instance, so code below returns a single well known global instance.

heap vat printing «

     Printing a heap vat just prints the stats:

     To use operator<<() when writing a heap vat to a sink, all you need is inlines as follows, declared in a C++ header file:

heap vat alloc «

     The heap vat allocation methods use malloc() to get the necessary space, but a cy_fix subclass named IovFixEtc, written in C++ shown below, is used to represent the space returned. Note the implementation of IovFixEtc clones the y8vn node subclass shown in the node thorn demo (cf «).

heap vat free «

     When the iov allocated by a heap vat hits zero references, it gets freed by calling the free method below, which checks for IovFixEtc instance corruption (due to underwrites or overwrites, for example) by checking for expected guard byte values before and after.

     Actually, two subclasses of cy_fix are shown below. The second, IovFixEtc, inherits from a base IovFix which only knows an iovec is involved. This allows base IovFix to be re-used later when free pools of single size iovs are allocated by another vat. Virtual methods are defined by IovFix and are re-used unchanged by subclass IovFixEtc. (This works because only the vat involved knows the iov is actually a IovFixEtc instance, and not another IovFix subtype.)

iov fix «

     Here are cy_fix virtual methods defined for IovFix:

     The IovFix struct adds members for refcount, iovec, and vat pointer.

     When refs hit zero, on_zero_refs is called to return this IovFix instance to the vat. Note this works even when the specific subclass of IovFix is not known.

iov fix etc «

     Now here's the actual concrete subclass of both cy_fix and IovFix used by cy_heapvat:

     The two bytes of member etc_v[2] provide space for a trailing null byte and a trailing 0xAA after-guard byte. Null termination is convenient when the iovec might be used as a C string, especially when viewed by debug tools.

     Note the length of the iovec is stored in the iov_len field in the iovec member of the IovFix base class.

iov fix constructor «

     The constructor assumes you have passed the right values for base and len. (When the subclass is IovFixEtc, those two values should be the address etc_v and the length of bytes allocated in excess of sizeof(IovFixEtc).)

iov fix addref «

iov fix delref «

iov fix current refs «

iov fix printing «

IovFixEtc constructor «

     Here's the constructor for leaf class IovFixEtc. Note the assumption that length passed is count bytes allocated in excess of sizeof(IovFixEtc).

IovFixEtc errors «

     When one of the magic numbers checked in actual concrete subclass of both egood() fails, here is where the problem is triaged, logged, and asserted:

     A pool is similar to a vat but assumes no refcounting, and further assumes no maximum size granularity is necessary. (Thus no complex bind method like one in cy_vat is needed.)

pool vtable «

     Pool methods cover only alloc, free, and print in cite format (one line only please).

pool constructor «

     The constructor just assigns function pointers:

pool dispatch «

     Inline methods dispatch virtual calls:

heap pool «

     The following concrete subclass of cy_vat is written in C and uses malloc() and free() for allocation. (So just like the heap vat class shown earlier, there's little need to have more than one global instance.)

     To be a subclass of cy_vat, the first member must be an instance of cy_vat. (A subclass in C++ can simply inherit cy_vat instead.)

heap pool constructor «

     The constructor constructs the base cy_vat class, then clears all counter statistics.

heap pool global «

     Here's a single global heap pool instance, which is not thread-safe in the statisics. Single threaded use is assumed here.

heap pool printing «

     Printing just exposes stats:

heap pool alloc «

heap pool free

     Here's a menu of pages on cy code.

• vector - std::vector clone
• bheap - binary min heap
• label - ascync descriptors
• misc - bunch of basic utils
• pool - C-based vats and pools
• deck - scatter/gather suite
• sink - C-based out stream api
• row - a new deck rewrite

     See license and copyright for code here. For more context, see the cy page.

     Compared to a thorn demo, I explain cy code less: I care little whether folks use or grasp cy source. But since I aim to get ideas across, I reveal a point to code constructs so you see intentions.

     If you ask: What was this for? That's the only question I address: why a thing was done. If you what to know how code works or what loose ends remain, figure it out.

     Library source code appears appears in amber (orange/brown):

     Source .cpp code appears in red:

     Sample test code is purple:

     Printed output on stdout is green:

     I know these aren't the best color cues. (Amber and green might appear the same hue to color blind folks. I have excellent color discrimination myself.)

     This page has no sample test code because the row page provides a basic integrated test of all these objects.