/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 * Common Development and Distribution License (the "License").

 * You may not use this file except in compliance with the License.

 *

 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

 * or http://www.opensolaris.org/os/licensing.

 * See the License for the specific language governing permissions

 * and limitations under the License.

 *

 * When distributing Covered Code, include this CDDL HEADER in each

 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.

 * If applicable, add the following below this CDDL HEADER, with the

 * fields enclosed by brackets "[]" replaced with your own identifying

 * information: Portions Copyright [yyyy] [name of copyright owner]

 *

 * CDDL HEADER END

 */

/*

 */

/*

 * Kernel memory allocator, as described in the following two papers and a

 * statement about the consolidator:

 *

 * Jeff Bonwick,

 * The Slab Allocator: An Object-Caching Kernel Memory Allocator.

 * Proceedings of the Summer 1994 Usenix Conference.

 * Available as /shared/sac/PSARC/1994/028/materials/kmem.pdf.

 *

 * Jeff Bonwick and Jonathan Adams,

 * Magazines and vmem: Extending the Slab Allocator to Many CPUs and

 * Arbitrary Resources.

 * Proceedings of the 2001 Usenix Conference.

 * Available as /shared/sac/PSARC/2000/550/materials/vmem.pdf.

 *

 * kmem Slab Consolidator Big Theory Statement:

 *

 * 1. Motivation

 *

 * As stated in Bonwick94, slabs provide the following advantages over other

 * allocation structures in terms of memory fragmentation:

 *

 *  - Internal fragmentation (per-buffer wasted space) is minimal.

 *  - Severe external fragmentation (unused buffers on the free list) is

 *    unlikely.

 *

 * Segregating objects by size eliminates one source of external fragmentation,

 * and according to Bonwick:

 *

 *   The other reason that slabs reduce external fragmentation is that all

 *   objects in a slab are of the same type, so they have the same lifetime

 *   distribution. The resulting segregation of short-lived and long-lived

 *   objects at slab granularity reduces the likelihood of an entire page being

 *   held hostage due to a single long-lived allocation [Barrett93, Hanson90].

 *

 * While unlikely, severe external fragmentation remains possible. Clients that

 * allocate both short- and long-lived objects from the same cache cannot

 * anticipate the distribution of long-lived objects within the allocator's slab

 * implementation. Even a small percentage of long-lived objects distributed

 * randomly across many slabs can lead to a worst case scenario where the client

 * frees the majority of its objects and the system gets back almost none of the

 * slabs. Despite the client doing what it reasonably can to help the system

 * reclaim memory, the allocator cannot shake free enough slabs because of

 * lonely allocations stubbornly hanging on. Although the allocator is in a

 * position to diagnose the fragmentation, there is nothing that the allocator

 * by itself can do about it. It only takes a single allocated object to prevent

 * an entire slab from being reclaimed, and any object handed out by

 * kmem_cache_alloc() is by definition in the client's control. Conversely,

 * although the client is in a position to move a long-lived object, it has no

 * way of knowing if the object is causing fragmentation, and if so, where to

 * move it. A solution necessarily requires further cooperation between the

 * allocator and the client.

 *

 * 2. Move Callback

 *

 * The kmem slab consolidator therefore adds a move callback to the

 * allocator/client interface, improving worst-case external fragmentation in

 * kmem caches that supply a function to move objects from one memory location

 * to another. In a situation of low memory kmem attempts to consolidate all of

 * a cache's slabs at once; otherwise it works slowly to bring external

 * fragmentation within the 1/8 limit guaranteed for internal fragmentation,

 * thereby helping to avoid a low memory situation in the future.

 *

 * The callback has the following signature:

 *

 *   kmem_cbrc_t move(void *old, void *new, size_t size, void *user_arg)

 *

 * It supplies the kmem client with two addresses: the allocated object that

 * kmem wants to move and a buffer selected by kmem for the client to use as the

 * copy destination. The callback is kmem's way of saying "Please get off of

 * this buffer and use this one instead." kmem knows where it wants to move the

 * object in order to best reduce fragmentation. All the client needs to know

 * about the second argument (void *new) is that it is an allocated, constructed

 * object ready to take the contents of the old object. When the move function

 * is called, the system is likely to be low on memory, and the new object

 * spares the client from having to worry about allocating memory for the

 * requested move. The third argument supplies the size of the object, in case a

 * single move function handles multiple caches whose objects differ only in

 * size (such as zio_buf_512, zio_buf_1024, etc). Finally, the same optional

 * user argument passed to the constructor, destructor, and reclaim functions is

 * also passed to the move callback.

 *

 * 2.1 Setting the Move Callback

 *

 * The client sets the move callback after creating the cache and before

 * allocating from it:

 *

 *	object_cache = kmem_cache_create(...);

 *      kmem_cache_set_move(object_cache, object_move);

 *

 * 2.2 Move Callback Return Values

 *

 * Only the client knows about its own data and when is a good time to move it.

 * The client is cooperating with kmem to return unused memory to the system,

 * and kmem respectfully accepts this help at the client's convenience. When

 * asked to move an object, the client can respond with any of the following:

 *

 *   typedef enum kmem_cbrc {

 *           KMEM_CBRC_YES,

 *           KMEM_CBRC_NO,

 *           KMEM_CBRC_LATER,

 *           KMEM_CBRC_DONT_NEED,

 *           KMEM_CBRC_DONT_KNOW

 *   } kmem_cbrc_t;

 *

 * The client must not explicitly kmem_cache_free() either of the objects passed

 * to the callback, since kmem wants to free them directly to the slab layer

 * (bypassing the per-CPU magazine layer). The response tells kmem which of the

 * objects to free:

 *

 *       YES: (Did it) The client moved the object, so kmem frees the old one.

 *        NO: (Never) The client refused, so kmem frees the new object (the

 *            unused copy destination). kmem also marks the slab of the old

 *            object so as not to bother the client with further callbacks for

 *            that object as long as the slab remains on the partial slab list.

 *            (The system won't be getting the slab back as long as the

 *            immovable object holds it hostage, so there's no point in moving

 *            any of its objects.)

 *     LATER: The client is using the object and cannot move it now, so kmem

 *            frees the new object (the unused copy destination). kmem still

 *            attempts to move other objects off the slab, since it expects to

 *            succeed in clearing the slab in a later callback. The client

 *            should use LATER instead of NO if the object is likely to become

 *            movable very soon.

 * DONT_NEED: The client no longer needs the object, so kmem frees the old along

 *            with the new object (the unused copy destination). This response

 *            is the client's opportunity to be a model citizen and give back as

 *            much as it can.

 * DONT_KNOW: The client does not know about the object because

 *            a) the client has just allocated the object and not yet put it

 *               wherever it expects to find known objects

 *            b) the client has removed the object from wherever it expects to

 *               find known objects and is about to free it, or

 *            c) the client has freed the object.

 *            In all these cases (a, b, and c) kmem frees the new object (the

 *            unused copy destination) and searches for the old object in the

 *            magazine layer. If found, the object is removed from the magazine

 *            layer and freed to the slab layer so it will no longer hold the

 *            slab hostage.

 *

 * 2.3 Object States

 *

 * Neither kmem nor the client can be assumed to know the object's whereabouts

 * at the time of the callback. An object belonging to a kmem cache may be in

 * any of the following states:

 *

 * 1. Uninitialized on the slab

 * 2. Allocated from the slab but not constructed (still uninitialized)

 * 3. Allocated from the slab, constructed, but not yet ready for business

 *    (not in a valid state for the move callback)

 * 4. In use (valid and known to the client)

 * 5. About to be freed (no longer in a valid state for the move callback)

 * 6. Freed to a magazine (still constructed)

 * 7. Allocated from a magazine, not yet ready for business (not in a valid

 *    state for the move callback), and about to return to state #4

 * 8. Deconstructed on a magazine that is about to be freed

 * 9. Freed to the slab

 *

 * Since the move callback may be called at any time while the object is in any

 * of the above states (except state #1), the client needs a safe way to

 * determine whether or not it knows about the object. Specifically, the client

 * needs to know whether or not the object is in state #4, the only state in

 * which a move is valid. If the object is in any other state, the client should

 * immediately return KMEM_CBRC_DONT_KNOW, since it is unsafe to access any of

 * the object's fields.

 *

 * Note that although an object may be in state #4 when kmem initiates the move

 * request, the object may no longer be in that state by the time kmem actually

 * calls the move function. Not only does the client free objects

 * asynchronously, kmem itself puts move requests on a queue where thay are

 * pending until kmem processes them from another context. Also, objects freed

 * to a magazine appear allocated from the point of view of the slab layer, so

 * kmem may even initiate requests for objects in a state other than state #4.

 *

 * 2.3.1 Magazine Layer

 *

 * An important insight revealed by the states listed above is that the magazine

 * layer is populated only by kmem_cache_free(). Magazines of constructed

 * objects are never populated directly from the slab layer (which contains raw,

 * unconstructed objects). Whenever an allocation request cannot be satisfied

 * from the magazine layer, the magazines are bypassed and the request is

 * satisfied from the slab layer (creating a new slab if necessary). kmem calls

 * the object constructor only when allocating from the slab layer, and only in

 * response to kmem_cache_alloc() or to prepare the destination buffer passed in

 * the move callback. kmem does not preconstruct objects in anticipation of

 * kmem_cache_alloc().

 *

 * 2.3.2 Object Constructor and Destructor

 *

 * If the client supplies a destructor, it must be valid to call the destructor

 * on a newly created object (immediately after the constructor).

 *

 * 2.4 Recognizing Known Objects

 *

 * There is a simple test to determine safely whether or not the client knows

 * about a given object in the move callback. It relies on the fact that kmem

 * guarantees that the object of the move callback has only been touched by the

 * client itself or else by kmem. kmem does this by ensuring that none of the

 * cache's slabs are freed to the virtual memory (VM) subsystem while a move

 * callback is pending. When the last object on a slab is freed, if there is a

 * pending move, kmem puts the slab on a per-cache dead list and defers freeing

 * slabs on that list until all pending callbacks are completed. That way,

 * clients can be certain that the object of a move callback is in one of the

 * states listed above, making it possible to distinguish known objects (in

 * state #4) using the two low order bits of any pointer member (with the

 * exception of 'char *' or 'short *' which may not be 4-byte aligned on some

 * platforms).

 *

 * The test works as long as the client always transitions objects from state #4

 * (known, in use) to state #5 (about to be freed, invalid) by setting the low

 * order bit of the client-designated pointer member. Since kmem only writes

 * invalid memory patterns, such as 0xbaddcafe to uninitialized memory and

 * 0xdeadbeef to freed memory, any scribbling on the object done by kmem is

 * guaranteed to set at least one of the two low order bits. Therefore, given an

 * object with a back pointer to a 'container_t *o_container', the client can

 * test

 *

 *      container_t *container = object->o_container;

 *      if ((uintptr_t)container & 0x3) {

 *              return (KMEM_CBRC_DONT_KNOW);

 *      }

 *

 * Typically, an object will have a pointer to some structure with a list or

 * hash where objects from the cache are kept while in use. Assuming that the

 * client has some way of knowing that the container structure is valid and will

 * not go away during the move, and assuming that the structure includes a lock

 * to protect whatever collection is used, then the client would continue as

 * follows:

 *

 *	// Ensure that the container structure does not go away.

 *      if (container_hold(container) == 0) {

 *              return (KMEM_CBRC_DONT_KNOW);

 *      }

 *      mutex_enter(&container->c_objects_lock);

 *      if (container != object->o_container) {

 *              mutex_exit(&container->c_objects_lock);

 *              container_rele(container);

 *              return (KMEM_CBRC_DONT_KNOW);

 *      }

 *

 * At this point the client knows that the object cannot be freed as long as

 * c_objects_lock is held. Note that after acquiring the lock, the client must

 * recheck the o_container pointer in case the object was removed just before

 * acquiring the lock.

 *

 * When the client is about to free an object, it must first remove that object

 * from the list, hash, or other structure where it is kept. At that time, to

 * mark the object so it can be distinguished from the remaining, known objects,

 * the client sets the designated low order bit:

 *

 *      mutex_enter(&container->c_objects_lock);

 *      object->o_container = (void *)((uintptr_t)object->o_container | 0x1);

 *      list_remove(&container->c_objects, object);

 *      mutex_exit(&container->c_objects_lock);

 *

 * In the common case, the object is freed to the magazine layer, where it may

 * be reused on a subsequent allocation without the overhead of calling the

 * constructor. While in the magazine it appears allocated from the point of

 * view of the slab layer, making it a candidate for the move callback. Most

 * objects unrecognized by the client in the move callback fall into this

 * category and are cheaply distinguished from known objects by the test

 * described earlier. Since recognition is cheap for the client, and searching

 * magazines is expensive for kmem, kmem defers searching until the client first

 * returns KMEM_CBRC_DONT_KNOW. As long as the needed effort is reasonable, kmem

 * elsewhere does what it can to avoid bothering the client unnecessarily.

 *

 * Invalidating the designated pointer member before freeing the object marks

 * the object to be avoided in the callback, and conversely, assigning a valid

 * value to the designated pointer member after allocating the object makes the

 * object fair game for the callback:

 *

 *      ... allocate object ...

 *      ... set any initial state not set by the constructor ...

 *

 *      mutex_enter(&container->c_objects_lock);

 *      list_insert_tail(&container->c_objects, object);

 *      membar_producer();

 *      object->o_container = container;

 *      mutex_exit(&container->c_objects_lock);

 *

 * Note that everything else must be valid before setting o_container makes the

 * object fair game for the move callback. The membar_producer() call ensures

 * that all the object's state is written to memory before setting the pointer

 * that transitions the object from state #3 or #7 (allocated, constructed, not

 * yet in use) to state #4 (in use, valid). That's important because the move

 * function has to check the validity of the pointer before it can safely

 * acquire the lock protecting the collection where it expects to find known

 * objects.

 *

 * This method of distinguishing known objects observes the usual symmetry:

 * invalidating the designated pointer is the first thing the client does before

 * freeing the object, and setting the designated pointer is the last thing the

 * client does after allocating the object. Of course, the client is not

 * required to use this method. Fundamentally, how the client recognizes known

 * objects is completely up to the client, but this method is recommended as an

 * efficient and safe way to take advantage of the guarantees made by kmem. If

 * the entire object is arbitrary data without any markable bits from a suitable

 * pointer member, then the client must find some other method, such as

 * searching a hash table of known objects.

 *

 * 2.5 Preventing Objects From Moving

 *

 * Besides a way to distinguish known objects, the other thing that the client

 * needs is a strategy to ensure that an object will not move while the client

 * is actively using it. The details of satisfying this requirement tend to be

 * highly cache-specific. It might seem that the same rules that let a client

 * remove an object safely should also decide when an object can be moved

 * safely. However, any object state that makes a removal attempt invalid is

 * likely to be long-lasting for objects that the client does not expect to

 * remove. kmem knows nothing about the object state and is equally likely (from

 * the client's point of view) to request a move for any object in the cache,

 * whether prepared for removal or not. Even a low percentage of objects stuck

 * in place by unremovability will defeat the consolidator if the stuck objects

 * are the same long-lived allocations likely to hold slabs hostage.

 * Fundamentally, the consolidator is not aimed at common cases. Severe external

 * fragmentation is a worst case scenario manifested as sparsely allocated

 * slabs, by definition a low percentage of the cache's objects. When deciding

 * what makes an object movable, keep in mind the goal of the consolidator: to

 * bring worst-case external fragmentation within the limits guaranteed for

 * internal fragmentation. Removability is a poor criterion if it is likely to

 * exclude more than an insignificant percentage of objects for long periods of

 * time.

 *

 * A tricky general solution exists, and it has the advantage of letting you

 * move any object at almost any moment, practically eliminating the likelihood

 * that an object can hold a slab hostage. However, if there is a cache-specific

 * way to ensure that an object is not actively in use in the vast majority of

 * cases, a simpler solution that leverages this cache-specific knowledge is

 * preferred.

 *

 * 2.5.1 Cache-Specific Solution

 *

 * As an example of a cache-specific solution, the ZFS znode cache takes

 * advantage of the fact that the vast majority of znodes are only being

 * referenced from the DNLC. (A typical case might be a few hundred in active

 * use and a hundred thousand in the DNLC.) In the move callback, after the ZFS

 * client has established that it recognizes the znode and can access its fields

 * safely (using the method described earlier), it then tests whether the znode

 * is referenced by anything other than the DNLC. If so, it assumes that the

 * znode may be in active use and is unsafe to move, so it drops its locks and

 * returns KMEM_CBRC_LATER. The advantage of this strategy is that everywhere

 * else znodes are used, no change is needed to protect against the possibility

 * of the znode moving. The disadvantage is that it remains possible for an

 * application to hold a znode slab hostage with an open file descriptor.

 * However, this case ought to be rare and the consolidator has a way to deal

 * with it: If the client responds KMEM_CBRC_LATER repeatedly for the same

 * object, kmem eventually stops believing it and treats the slab as if the

 * client had responded KMEM_CBRC_NO. Having marked the hostage slab, kmem can

 * then focus on getting it off of the partial slab list by allocating rather

 * than freeing all of its objects. (Either way of getting a slab off the

 * free list reduces fragmentation.)

 *

 * 2.5.2 General Solution

 *

 * The general solution, on the other hand, requires an explicit hold everywhere

 * the object is used to prevent it from moving. To keep the client locking

 * strategy as uncomplicated as possible, kmem guarantees the simplifying

 * assumption that move callbacks are sequential, even across multiple caches.

 * Internally, a global queue processed by a single thread supports all caches

 * implementing the callback function. No matter how many caches supply a move

 * function, the consolidator never moves more than one object at a time, so the

 * client does not have to worry about tricky lock ordering involving several

 * related objects from different kmem caches.

 *

 * The general solution implements the explicit hold as a read-write lock, which

 * allows multiple readers to access an object from the cache simultaneously

 * while a single writer is excluded from moving it. A single rwlock for the

 * entire cache would lock out all threads from using any of the cache's objects

 * even though only a single object is being moved, so to reduce contention,

 * the client can fan out the single rwlock into an array of rwlocks hashed by

 * the object address, making it probable that moving one object will not

 * prevent other threads from using a different object. The rwlock cannot be a

 * member of the object itself, because the possibility of the object moving

 * makes it unsafe to access any of the object's fields until the lock is

 * acquired.

 *

 * Assuming a small, fixed number of locks, it's possible that multiple objects

 * will hash to the same lock. A thread that needs to use multiple objects in

 * the same function may acquire the same lock multiple times. Since rwlocks are

 * reentrant for readers, and since there is never more than a single writer at

 * a time (assuming that the client acquires the lock as a writer only when

 * moving an object inside the callback), there would seem to be no problem.

 * However, a client locking multiple objects in the same function must handle

 * one case of potential deadlock: Assume that thread A needs to prevent both

 * object 1 and object 2 from moving, and thread B, the callback, meanwhile

 * tries to move object 3. It's possible, if objects 1, 2, and 3 all hash to the

 * same lock, that thread A will acquire the lock for object 1 as a reader

 * before thread B sets the lock's write-wanted bit, preventing thread A from

 * reacquiring the lock for object 2 as a reader. Unable to make forward

 * progress, thread A will never release the lock for object 1, resulting in

 * deadlock.

 *

 * There are two ways of avoiding the deadlock just described. The first is to

 * use rw_tryenter() rather than rw_enter() in the callback function when

 * attempting to acquire the lock as a writer. If tryenter discovers that the

 * same object (or another object hashed to the same lock) is already in use, it

 * aborts the callback and returns KMEM_CBRC_LATER. The second way is to use

 * rprwlock_t (declared in common/fs/zfs/sys/rprwlock.h) instead of rwlock_t,

 * since it allows a thread to acquire the lock as a reader in spite of a

 * waiting writer. This second approach insists on moving the object now, no

 * matter how many readers the move function must wait for in order to do so,

 * and could delay the completion of the callback indefinitely (blocking

 * callbacks to other clients). In practice, a less insistent callback using

 * rw_tryenter() returns KMEM_CBRC_LATER infrequently enough that there seems

 * little reason to use anything else.

 *

 * Avoiding deadlock is not the only problem that an implementation using an

 * explicit hold needs to solve. Locking the object in the first place (to

 * prevent it from moving) remains a problem, since the object could move

 * between the time you obtain a pointer to the object and the time you acquire

 * the rwlock hashed to that pointer value. Therefore the client needs to

 * recheck the value of the pointer after acquiring the lock, drop the lock if

 * the value has changed, and try again. This requires a level of indirection:

 * something that points to the object rather than the object itself, that the

 * client can access safely while attempting to acquire the lock. (The object

 * itself cannot be referenced safely because it can move at any time.)

 * The following lock-acquisition function takes whatever is safe to reference

 * (arg), follows its pointer to the object (using function f), and tries as

 * often as necessary to acquire the hashed lock and verify that the object

 * still has not moved:

 *

 *      object_t *

 *      object_hold(object_f f, void *arg)

 *      {

 *              object_t *op;

 *

 *              op = f(arg);

 *              if (op == NULL) {

 *                      return (NULL);

 *              }

 *

 *              rw_enter(OBJECT_RWLOCK(op), RW_READER);

 *              while (op != f(arg)) {

 *                      rw_exit(OBJECT_RWLOCK(op));

 *                      op = f(arg);

 *                      if (op == NULL) {

 *                              break;

 *                      }

 *                      rw_enter(OBJECT_RWLOCK(op), RW_READER);

 *              }

 *

 *              return (op);

 *      }

 *

 * The OBJECT_RWLOCK macro hashes the object address to obtain the rwlock. The

 * lock reacquisition loop, while necessary, almost never executes. The function

 * pointer f (used to obtain the object pointer from arg) has the following type

 * definition:

 *

 *      typedef object_t *(*object_f)(void *arg);

 *

 * An object_f implementation is likely to be as simple as accessing a structure

 * member:

 *

 *      object_t *

 *      s_object(void *arg)

 *      {

 *              something_t *sp = arg;

 *              return (sp->s_object);

 *      }

 *

 * The flexibility of a function pointer allows the path to the object to be

 * arbitrarily complex and also supports the notion that depending on where you

 * are using the object, you may need to get it from someplace different.

 *

 * The function that releases the explicit hold is simpler because it does not

 * have to worry about the object moving:

 *

 *      void

 *      object_rele(object_t *op)

 *      {

 *              rw_exit(OBJECT_RWLOCK(op));

 *      }