I’m trying to learn UMA or general-purpose kernel object allocator through the kernel source code. This approach maybe weird, but the FreeBSD source code is organized and clear. Worth mentioning that it’s documentation inside source code and has its own manual uma(9).

What is UMA?

Let’s look at the manual first:

UMA (Universal Memory Allocator) provides an efficient interface for managing dynamically-sized collections of items of identical size, referred to as zones.

Looks like UMA directly responsible for zones. But, what are zones? The manual continues with:

Zones keep track of which items are in use and which are not, and UMA provides functions for allocating items from a zone and for releasing them back, making them available for subsequent allocation requests.

Ok, I should start looking for its code.

Where to start?

As defined in SYNOPSIS of UMA(9), the source code resides in /usr/src/sys/vm/. So let’s list files with uma in their names.

[spmzt@cornelia] [/usr/src/sys/vm] % ls *uma*              
uma_align_mask.h	uma_core.c		uma_dbg.c		uma_dbg.h		uma_int.h		uma.h

By seeing their namees, I instantly know I should start with uma_core.c for the main code and uma.h for it’s header.

Now, I probably should looking for zone structures, let’s open the uma.h first.

/* Types and type defs */
struct uma_zone;

uma_zone structure is the first structure defined in the system. However, as you can see, it’s a forward declaration. We should find it. If you familiar with style(9), you can easily find your desired code in the FreeBSD kernel.

[root@cornelia] [/usr/src/sys/vm] # grep -ri '^struct uma_zone {'
uma_int.h:struct uma_zone {

Yup, it did the trick. our main zone structure is defined in uma_int.h. After, I opened the uma_int.h file, I saw more than hundered of documentation at the beginning of the file.

Here is the break down of what it says.

Zone

…Zones describe unique allocation types. Zones are

  • organized into per-CPU caches which are filled by buckets.

Bucket

…Buckets are

  • organized according to memory domains. Buckets are filled from kegs which
  • are also organized according to memory domains.

Keg

… Kegs describe a unique

  • allocation type, backend memory provider, and layout. Kegs are associated
  • with one or more zones and zones reference one or more kegs.

Slab

…Kegs provide

  • slabs which are virtually contiguous collections of pages. Each slab is
  • broken down int one or more items that will satisfy an individual allocation.

At the end of its brief summary, there is an ASCII representation of a slab.

/*
 *  This is the representation for normal (Non OFFPAGE slab)
 *
 *  i == item
 *  s == slab pointer
 *
 *  <----------------  Page (UMA_SLAB_SIZE) ------------------>
 *  ___________________________________________________________
 *     | _  _  _  _  _  _  _  _  _  _  _  _  _  _  _   ___________ |
 *     ||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i| |slab header||
 *     ||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_| |___________|| 
 *     |___________________________________________________________|
 *
 *
 *  This is an OFFPAGE slab. These can be larger than UMA_SLAB_SIZE.
 *
 *  ___________________________________________________________
 *     | _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _   |
 *     ||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i|  |
 *     ||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_|  |
 *     |___________________________________________________________|
 *       ___________    ^
 *  |slab header|   |
 *  |___________|---*
 *
 */

So, we have a slab type which called normal or non OFFPAGE slab that its slab header is located at the end of the allocated page. Also, there is an OFFPAGE slab, it can be larger than UMA_SLAB_SIZE which is currently defined as a PAGE_SIZE (which is 4096 bytes in my laptop.). How I know that? using sysctl hw.pagesize you can findout your own pagesize. Typically, it is 4096 bytes in x86 architectures. Back to OFFPAGE slab, it uses a separate slab header outside the allocated page.

Continuing on uma_zone structure, it has a lot of fields inside its struct. Some of them catches my attention:

uint32_t    uz_size;    /* Size inherited from kegs */
uint64_t    uz_max_items;   /* Maximum number of items to alloc */

We have size of each object and the maximum number of objects in here.

uma_ctor    uz_ctor;    /* Constructor for each allocation */
uma_dtor    uz_dtor;    /* Destructor */

ctor and dtor is described in UMA(9) manual:

The ctor and dtor arguments are callback functions that are called by the UMA subsystem at the time of the call to uma_zalloc() and uma_zfree() respectively. Their purpose is to provide hooks for initializing or destroying things that need to be done at the time of the allocation or release of a resource. A good usage for the ctor and dtor callbacks might be to initialize a data structure embedded in the item, such as a queue(3) head.

In summary, we use them to initialize a data structure in the items at the time of allocation or release of a resource.

uint16_t    uz_bucket_size; /* Number of items in full bucket */
uint16_t    uz_bucket_size_max; /* Maximum number of bucket items */

These are used for defining the number of items in full bucket of a zone and its max limitation of items in that those buckets.

const char  *uz_name;   /* Text name of the zone */

The name of the zone defined here.

uma_init    uz_init;    /* Initializer for each item */
uma_fini    uz_fini;    /* Finalizer for each item. */

The init and fini are described in UMA(9) too:

The zinit and zfini arguments are used to optimize the allocation of items from the zone. They are called by the UMA subsystem whenever it needs to allocate or free items to satisfy requests or memory pressure. A good use for the zinit and zfini callbacks might be to initialize and destroy a mutex contained within an item. This would allow one to avoid destroying and re-initializing the mutex each time the item is freed and re-allocated.

memory pressure is refered to pageout daemon, which is the only process that ask the UMA to free its items to free memory.

LIST_ENTRY(uma_zone) uz_link;   /* List of all zones in keg */
uma_keg_t   uz_keg;     /* This zone's keg if !CACHE */

Finally, here is a pointer from zone to keg. We probably should move to the keg structure to see what actually are they. You can find the uma_keg structure in the file we are currently looking at.

LIST_HEAD(,uma_zone)    uk_zones;   /* Keg's zones */

This field in uma_keg shows us the keg can have multiple zones connected together using a linked list.

uint32_t    uk_size;    /* Requested size of each item */
uint32_t    uk_rsize;   /* Real size of each item */

These struct members are the one that zone inherited the size from them. So which one it uses?

You see these two lines under the zone_ctor function. The one who initializes all fields, lock, etc for a zone:

 zone->uz_keg = keg;
 zone->uz_size = keg->uk_size;

So it’s the requested size of each item stored in zone struct, not the real size.

uma_init    uk_init;    /* Keg's init routine */
uma_fini    uk_fini;    /* Keg's fini routine */

As you can see, we have uma_init and uma_fini for kegs too.

uma_alloc   uk_allocf;  /* Allocation function */
uma_free    uk_freef;   /* Free routine */

uint16_t    uk_ipers;   /* Items per slab */

As we follow the structure, we can see a clear hierarchy in normal zone. Zones have number of items, and keg have their own number of items per slab.

const char  *uk_name;       /* Name of creating zone. *

Here is the name of the keg, as defined in comment of the code, it uses the same of zone name. I can confirm it in the keg_ctor function:

keg->uk_name = zone->uz_name;

And last but not least:

LIST_ENTRY(uma_keg) uk_link;    /* List of all kegs */

All of the kegs linked together.

Now it’s time to move to the uma_slab structure. The structure is simple and self explaining. Here is the full structure:

/*
 * The slab structure manages a single contiguous allocation from backing
 * store and subdivides it into individually allocatable items.
 */
struct uma_slab {
    LIST_ENTRY(uma_slab)    us_link;    /* slabs in zone */
    uint16_t    us_freecount;       /* How many are free? */
    uint8_t     us_flags;       /* Page flags see uma.h */
    uint8_t     us_domain;      /* Backing NUMA domain. */
    struct noslabbits us_free;      /* Free bitmask, flexible. */
};

The only struct member that may need explaining is free bitmask. Bitmask simply represent free and allocated items.

To be continued…