ucx1-sys 0.1.0

/**
 * Copyright (C) Mellanox Technologies Ltd. 2001-2015.  ALL RIGHTS RESERVED.
 *
 * See file LICENSE for terms.
 */

#ifndef UCS_PGTABLE_H_
#define UCS_PGTABLE_H_

#include <ucs/config/types.h>
#include <ucs/sys/compiler_def.h>
#include <ucs/type/status.h>

/*
 * The Page Table data structure organizes non-overlapping regions of memory in
 * an efficient radix tree, optimized for large and/or aligned regions.
 *
 * A page table entry can point to either a region (indicated by setting the
 * UCS_PGT_PTE_FLAG_REGION bit), or another entry (indicated by UCS_PGT_PTE_FLAG_DIR),
 * or be empty - if none of these bits is set.
 *
 */



/* Address alignment requirements */
#define UCS_PGT_ADDR_SHIFT         4
#define UCS_PGT_ADDR_ALIGN         (1ul << UCS_PGT_ADDR_SHIFT)
#define UCS_PGT_ADDR_ORDER          (sizeof(ucs_pgt_addr_t) * 8)
#define UCS_PGT_ADDR_MAX           ((ucs_pgt_addr_t)-1)

/* Page table entry/directory constants */
#define UCS_PGT_ENTRY_SHIFT        4
#define UCS_PGT_ENTRIES_PER_DIR    (1ul << (UCS_PGT_ENTRY_SHIFT))
#define UCS_PGT_ENTRY_MASK         (UCS_PGT_ENTRIES_PER_DIR - 1)

/* Page table pointers constants and flags */
#define UCS_PGT_ENTRY_FLAG_REGION  UCS_BIT(0)
#define UCS_PGT_ENTRY_FLAG_DIR     UCS_BIT(1)
#define UCS_PGT_ENTRY_FLAGS_MASK   (UCS_PGT_ENTRY_FLAG_REGION|UCS_PGT_ENTRY_FLAG_DIR)
#define UCS_PGT_ENTRY_PTR_MASK     (~UCS_PGT_ENTRY_FLAGS_MASK)
#define UCS_PGT_ENTRY_MIN_ALIGN    (UCS_PGT_ENTRY_FLAGS_MASK + 1)

/* Declare a variable as aligned so it could be placed in page table entry */
#define UCS_PGT_ENTRY_V_ALIGNED    UCS_V_ALIGNED(UCS_PGT_ENTRY_MIN_ALIGN > sizeof(long) ? \
                                                 UCS_PGT_ENTRY_MIN_ALIGN : sizeof(long))


#define UCS_PGT_REGION_FMT            "%p [0x%lx..0x%lx]"
#define UCS_PGT_REGION_ARG(_region)   (_region), (_region)->start, (_region)->end


/* Define the address type */
typedef unsigned long              ucs_pgt_addr_t;

/* Forward declarations */
typedef struct ucs_pgtable         ucs_pgtable_t;
typedef struct ucs_pgt_region      ucs_pgt_region_t;
typedef struct ucs_pgt_entry       ucs_pgt_entry_t;
typedef struct ucs_pgt_dir         ucs_pgt_dir_t;


/**
 * Callback for allocating a page table directory.
 *
 * @param [in]  pgtable  Pointer to the page table to allocate the directory for.
 *
 * @return Pointer to newly allocated pgdir, or NULL if failed. The pointer must
 *         be aligned to UCS_PGT_ENTRY_ALIGN boundary.
 * */
typedef ucs_pgt_dir_t* (*ucs_pgt_dir_alloc_callback_t)(const ucs_pgtable_t *pgtable);


/**
 * Callback for releasing a page table directory.
 *
 * @param [in]  pgtable  Pointer to the page table to in which the directory was
 *                       allocated.
 * @param [in]  pgdir    Page table directory to release.
 */
typedef void (*ucs_pgt_dir_release_callback_t)(const ucs_pgtable_t *pgtable,
                                               ucs_pgt_dir_t *pgdir);


/**
 * Callback for searching for regions in the page table.
 *
 * @param [in]  pgtable  The page table.
 * @param [in]  region   Found region.
 * @param [in]  arg      User-defined argument.
 */
typedef void (*ucs_pgt_search_callback_t)(const ucs_pgtable_t *pgtable,
                                          ucs_pgt_region_t *region, void *arg);


/**
 * Memory region in the page table.
 * The structure itself, and the pointers in it, must be aligned to 2^PTR_SHIFT.
 */
struct ucs_pgt_region {
    ucs_pgt_addr_t                 start; /**< Region start address */
    ucs_pgt_addr_t                 end;   /**< Region end address */
} UCS_PGT_ENTRY_V_ALIGNED;


/**
 * Page table entry:
 *
 * +--------------------+---+---+
 * |    pointer (MSB)   | d | r |
 * +--------------------+---+---+
 * |                    |   |   |
 * 64                   2   1   0
 *
 */
struct ucs_pgt_entry {
    ucs_pgt_addr_t                 value;  /**< Pointer + type bits. Can point
                                                to either a @ref ucs_pgt_dir_t or
                                                a @ref ucs_pgt_region_t. */
};


/**
 * Page table directory.
 */
struct ucs_pgt_dir {
    ucs_pgt_entry_t                entries[UCS_PGT_ENTRIES_PER_DIR];
    unsigned                       count;       /**< Number of valid entries */
};


/* Page table structure */
struct ucs_pgtable {

    /* Maps addresses whose (63-shift) high bits equal to value
     * This means: value * (2**shift) .. value * (2**(shift+1)) - 1
     */
    ucs_pgt_entry_t                root;        /**< root entry */
    ucs_pgt_addr_t                 base;        /**< base address */
    ucs_pgt_addr_t                 mask;        /**< mask for page table address range */
    unsigned                       shift;       /**< page table address span is 2**shift */
    unsigned                       num_regions; /**< total number of regions */
    ucs_pgt_dir_alloc_callback_t   pgd_alloc_cb;
    ucs_pgt_dir_release_callback_t pgd_release_cb;
};


/**
 * Initialize a page table.
 *
 * @param [in]  pgtable     Page table to initialize.
 * @param [in]  alloc_cb    Callback that will be used to allocate page directory,
 *                           which is the basic building block of the page table
 *                           data structure. This may allow the page table functions
 *                           to be safe to use from memory allocation context.
 * @param [in]  release_cb  Callback to release memory which was allocated by alloc_cb.
 */
ucs_status_t ucs_pgtable_init(ucs_pgtable_t *pgtable,
                              ucs_pgt_dir_alloc_callback_t alloc_cb,
                              ucs_pgt_dir_release_callback_t release_cb);

/**
 * Cleanup the page table and release all associated memory.
 *
 * @param [in]  pgtable     Page table to initialize.
 */
void ucs_pgtable_cleanup(ucs_pgtable_t *pgtable);


/**
 * Add a memory region to the page table.
 *
 * @param [in]  pgtable     Page table to insert the region to.
 * @param [in]  region      Memory region to insert. The region must remain valid
 *                           and unchanged s long as it's in the page table.
 *
 * @return UCS_OK - region was added.
 *         UCS_ERR_INVALID_PARAM - memory region address in invalid (misaligned or empty)
 *         UCS_ERR_ALREADY_EXISTS - the region overlaps with existing region.
 *
 */
ucs_status_t ucs_pgtable_insert(ucs_pgtable_t *pgtable, ucs_pgt_region_t *region);


/**
 * Remove a memory region from the page table.
 *
 * @param [in]  pgtable     Page table to remove the region from.
 * @param [in]  region      Memory region to remove. This must be the same pointer
 *                           passed to @ref ucs_pgtable_insert.
 *
 * @return UCS_OK - region was removed.
 *         UCS_ERR_INVALID_PARAM - memory region address in invalid (misaligned or empty)
 *         UCS_ERR_ALREADY_EXISTS - the region overlaps with existing region.
 *
 */
ucs_status_t ucs_pgtable_remove(ucs_pgtable_t *pgtable, ucs_pgt_region_t *region);


/*
 * Find a region which contains the given address.
 *
 * @param [in]  pgtable     Page table to search the address in.
 * @param [in]  address     Address to search.
 *
 * @return Region which contains 'address', or NULL if not found.
 */
ucs_pgt_region_t *ucs_pgtable_lookup(const ucs_pgtable_t *pgtable,
                                     ucs_pgt_addr_t address);


/**
 * Search for all regions overlapping with a given address range.
 *
 * @param [in]  pgtable     Page table to search the range in.
 * @param [in]  from        Lower bound of the range.
 * @param [in]  to          Upper bound of the range (inclusive).
 * @param [in]  cb          Callback to be called for every region found.
 *                           The callback must not modify the page table.
 * @param [in]  arg         User-defined argument to the callback.
 */
void ucs_pgtable_search_range(const ucs_pgtable_t *pgtable,
                              ucs_pgt_addr_t from, ucs_pgt_addr_t to,
                              ucs_pgt_search_callback_t cb, void *arg);


/**
 * Remove all regions from the page table and call the provided callback for each.
 *
 * @param [in]  pgtable     Page table to clean up.
 * @param [in]  cb          Callback to be called for every region, after it (and
 *                           all others) are removed.
 *                           The callback must not modify the page table.
 * @param [in]  arg         User-defined argument to the callback.
 */
void ucs_pgtable_purge(ucs_pgtable_t *pgtable, ucs_pgt_search_callback_t cb,
                       void *arg);


/**
 * Dump page table to log.
 *
 * @param [in]  pgtable      Page table to dump.
 * @param [in]  log_level    Which log level to use.
 */
void ucs_pgtable_dump(const ucs_pgtable_t *pgtable, ucs_log_level_t log_level);


/**
 * @return >Number of regions currently present in the page table.
 */
static inline unsigned ucs_pgtable_num_regions(const ucs_pgtable_t *pgtable)
{
    return pgtable->num_regions;
}


#endif