Updated `README.md` with instructions for building/using the kernel module.

[xeon-phi-kernel-module] / micscif / micscif_va_gen.c

/*
 * Copyright 2010-2017 Intel Corporation.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License, version 2,
 * as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * Disclaimer: The codes contained in these modules may be specific to
 * the Intel Software Development Platform codenamed Knights Ferry,
 * and the Intel product codenamed Knights Corner, and are not backward
 * compatible with other Intel products. Additionally, Intel will NOT
 * support the codes or instruction set in future products.
 *
 * Intel offers no warranty of any kind regarding the code. This code is
 * licensed on an "AS IS" basis and Intel is not obligated to provide
 * any support, assistance, installation, training, or other services
 * of any kind. Intel is also not obligated to provide any updates,
 * enhancements or extensions. Intel specifically disclaims any warranty
 * of merchantability, non-infringement, fitness for any particular
 * purpose, and any other warranty.
 *
 * Further, Intel disclaims all liability of any kind, including but
 * not limited to liability for infringement of any proprietary rights,
 * relating to the use of the code, even if Intel is notified of the
 * possibility of such liability. Except as expressly stated in an Intel
 * license agreement provided with this code and agreed upon with Intel,
 * no license, express or implied, by estoppel or otherwise, to any
 * intellectual property rights is granted herein.
 */

/* ************************************************************************* *\
generate a virtual address for a given size
\* ************************************************************************* */
#include "mic/micscif.h"

/* ************************************************************************* *\
FUNCTION: VaGenAddress::Initialize

DESCRIPTION: Initialize VaGenAddress to point to one node of size = range
\* ************************************************************************* */
static int
va_gen_init_internal(struct va_gen_addr *addr, uint64_t range)
{
	struct va_node *node;
	int err;

	va_node_init(&addr->allocator);
	if ((err = va_node_alloc(&addr->allocator, &addr->hole_list)) < 0)
		goto init_err;
	if (va_node_is_valid(addr->hole_list)) {
		node = va_node_get(&addr->allocator, addr->hole_list);
		node->next = invalid_va_node_index;
		node->base = 0;
		node->range = range;
	}
	addr->claims_list = invalid_va_node_index;
init_err:
	return err;
}

/* ************************************************************************* *\
FUNCTION:   VaGenAddress::Alloc
Allocate virtual memory by searching through free virtual memory
linked list for first range >= desired range.

Note: Free list is sorted by base, we are searching for range.

Return:     Offset to allocated virtual address if successful (in pages).
INVALID_VA_PAGE_INDEX if failed
\* ************************************************************************* */
static uint64_t
va_gen_alloc_internal(struct va_gen_addr *addr, uint64_t range)
{
	//==========================================================================
	// Search for a sufficiently large memory hole (first-fit).
	//--------------------------------------------------------------------------

	// Search for first available hole of sufficient size.
	uint32_t index = addr->hole_list;
	struct va_node *pFind;
	// Used to handle case of an exact range match.
	struct va_node *pPrev = 0;
	uint64_t base;

	if (0 == range || !va_node_is_valid(addr->hole_list))
		return INVALID_VA_PAGE_INDEX;

	pFind = va_node_get(&addr->allocator, index);

	for ( ; ; ) {
		if (pFind->range >= range)
			break;
		else {
			index = pFind->next;
			// No hole sufficiently large.
			if (!va_node_is_valid(index))
				return INVALID_VA_PAGE_INDEX;
			pPrev = pFind;
			pFind = va_node_get(&addr->allocator, index);
		}
	}

	// Found an adequate hole. Get its base.
	base = pFind->base;

	//============================================================================
	// Uncommon case: pFind->range == in_range
	// Remove node from the hole list when exact fit. Note, could leave the
	// hole list empty.
	//----------------------------------------------------------------------------

	if (pFind->range == range) {
		// first node?
		if (addr->hole_list == index)
			addr->hole_list = pFind->next;
		else {
			BUG_ON(!pPrev);
			pPrev->next = pFind->next;
		}
		va_node_free(&addr->allocator, index);
		return base;
	}

	//================================================================================
	// Shrink an existing node that is too large.
	//--------------------------------------------------------------------------------

	else {
		pFind->base  += range;
		pFind->range -= range;
	}

	return base;
}

/* ************************************************************************* *\
FUNCTION: VaGenAddress::FreeClaim

DESCRIPTION:
Removes claimed range from the claims list.
\* ************************************************************************* */
static void
va_gen_free_claim(struct va_gen_addr *addr, uint64_t base, uint64_t range)
{
	struct va_node *pNode = 0;
	struct va_node *pPrev = 0;
	uint32_t index, new_index;
	struct va_node *pNewNode;
	int err;

	if (0 == range)
		return;

	for (index = addr->claims_list; va_node_is_valid(index); index = pNode->next) {
		pNode = va_node_get(&addr->allocator, index);

		if (pNode->base <= base && pNode->base + pNode->range >= base + range) {
			if (pNode->base == base) {
				pNode->base += range;
				pNode->range -= range;
				if (0 == pNode->range) {
					if (pPrev)
						pPrev->next = pNode->next;
					else
						addr->claims_list = pNode->next;
					va_node_free(&addr->allocator, index);
				}
			} else if (pNode->base + pNode->range == base + range) {
				pNode->range -= range;
			} else {
				err = va_node_alloc(&addr->allocator, &new_index);
				BUG_ON(err < 0);
				pNewNode = va_node_get(&addr->allocator, new_index);
				pNewNode->base = base + range;
				pNewNode->range = pNode->range - pNewNode->base;
				pNewNode->next = pNode->next;
				pNode->range = base - pNode->base;
				pNode->next = new_index;
			}
			return;
		}
		if (pNode->base > base + range) {
			pr_debug("Freed claim not found in the list\n");
			return;
		}

		if ((pNode->base < base) ?
				(pNode->base + pNode->range > base) :
				(base + range > pNode->base)) {
			pr_debug("Freed claim partially overlaps the list\n");
			return;
		}
		pPrev = pNode;
	}
}

/* ************************************************************************* *\
FUNCTION: VaGenAddress::InsertAndCoalesce

DESCRIPTION:
O(n) search through free list sorted by base
should average O(n/2), and free list should be much less than the # allocated
coalesce with node before/after if possible
3 possible outcomes:
1.  freed node is inserted into list (0 deallocated)
2.  freed node range coalesced with existing node,
so freed node can be deallocated (1 deallocated)
3.  freed node + another node are coalesced + deallocated
(2 deallocated)
Fails if there is full or partial overlap between inserted
range and ranges in the list

returns false if insert failed
\* ************************************************************************* */
static int
va_gen_insert_and_coalesce(struct va_node_allocator *allocator, uint32_t *list,
			   uint64_t base, uint64_t range)
{
	// search through free list, insert ordered
	// also check for coalesce
	uint32_t findPtr = *list;
	uint32_t prev = *list;
	uint64_t end_range = base + range;
	uint32_t nextPtr, ptr;
	struct va_node *nextNode, *node;
	int err;

	while (va_node_is_valid(findPtr)) {
		struct va_node *find = va_node_get(allocator, findPtr);
		// overlap?
		//    A.start < B.start && A.end > B.start    A-B==A-B A-B==B-A otherwise A-A B-B
		//    B.start < A.start && B.end > A.start    B-A==B-A B-A==A-B otherwise B-B A-A
		//    =>
		//    A.start < B.start ? A.end > B.start : B.end > A.start

		if ((find->base < base) ?
				(find->base + find->range > base) :
				(end_range > find->base)) {
			return -1;
		}
		//----------------------------------------------------------
		// coalesce?  2 possibilities:
		//   1. (pFind->base + pFind->range) == current.base
		//      coalesce, check next node base = endrange,
		//         coalesce with next if possible, deallocate next, exit
		//   2. end_range == pFind->base
		//      coalesce, exit
		if (end_range == find->base) {
			// pr_debug("Coalesce base %lld before %lld\n", base, find->base);
			find->base = base;
			find->range += range;
			return 0;
		} else if ((find->base + find->range) == base) {
			// pr_debug("Coalesce base %lld after %lld\n", base, find->base);
			// leave the base unchanged
			find->range += range;
			// check the next node to see if it coalesces too
			nextPtr = find->next;
			if (va_node_is_valid(nextPtr)) {
				nextNode = va_node_get(allocator, nextPtr);
				// end_range is the same after prior coalesce
				if (nextNode->base == end_range) {
					// pr_debug("Double Coalesce index %d before %d\n", findPtr, nextPtr);
					find->range += nextNode->range;
					find->next = nextNode->next;
					va_node_free(allocator, nextPtr);
				}
			}
			return 0;
		}
		// end coalesce

		//----------------------------------------------------------
		// insert if found a node at a greater address
		else if (find->base > end_range)
			// exit loop, insert node
			break;
		// nothing found yet, next index
		prev = findPtr;
		findPtr = find->next;
	}

	//----------------------------------------------------------
	// insert or append if node
	//   could be at the end or empty free list (find index = INVALID)
	//   or, next node has larger base
	//----------------------------------------------------------
	err = va_node_alloc(allocator, &ptr);
	BUG_ON(err < 0);
	if (!va_node_is_valid(ptr)) {
		printk(KERN_ERR "FAILED to add hole!  base = %lld, range = %lld\n", base, range);
		return 0;
	}
	node = va_node_get(allocator, ptr);
	node->base = base;
	node->range = range;
	node->next = findPtr;
	// First node or empty list (Alloc() can empty the list)
	if (findPtr == *list)
		// pr_debug("List now starts with %d\n", ptr);
		*list = ptr;
	else { // reached the end of the list or insertion
		BUG_ON(!va_node_is_valid(prev));
		// pr_debug("Append index %d after %d\n", ptr, prev);
		(va_node_get(allocator, prev))->next = ptr;
	}
	return 0;
}

/* ************************************************************************* *\
FUNCTION: VaGenAddress::Free

DESCRIPTION:
Frees allocated Virtual Address. Inserts freed range in the list of holes
(available virtual addresses)
\* ************************************************************************* */
static void
va_gen_free_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range)
{
	int result = va_gen_insert_and_coalesce(&addr->allocator, &addr->hole_list, base, range);
	BUG_ON(result < 0);
}

/* ************************************************************************* *\
FUNCTION:   VaGenAddress::Alloc
Allocate virtual memory space.

Note: "Quick and dirty" implementation of aligned Alloc on top of
non-aligned Alloc.

Return:     Offset to allocated virtual address if successful (in pages).
INVALID_VA_PAGE_INDEX if failed
\* ************************************************************************* */
static uint64_t
va_gen_alloc_aligned(struct va_gen_addr *addr, uint64_t range, uint32_t unit_align)
{
	uint64_t base_address = va_gen_alloc_internal(addr, range + unit_align - 1);
	uint64_t aligned_base = base_address;
	if (0 == range || 0 == unit_align)
		return INVALID_VA_PAGE_INDEX;
	//BUG_ON(IsPowerOfTwo(in_unitAlign));

	if (unit_align == 1 || base_address == INVALID_VA_PAGE_INDEX)
		return base_address;

	if (aligned_base > base_address)
		va_gen_free_internal(addr, base_address, aligned_base - base_address);

	if (aligned_base + range < base_address + unit_align - 1)
		va_gen_free_internal(addr, aligned_base + range,
				base_address + unit_align - 1 - aligned_base - range);
	return aligned_base;
}

/* ************************************************************************* *\
FUNCTION: VaGenAddress::Claim

DESCRIPTION:
Claims a SVAS range. Checks if range was claimed before; if not, records
the claim in the claims list

returns false if claim failed
\* ************************************************************************* */
static int
va_gen_claim_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range)
{
	return va_gen_insert_and_coalesce(&addr->allocator, &addr->claims_list, base, range);
}

/* ************************************************************************* *\
FUNCTION:   VaGenAddressMutex::Alloc
Allocate virtual memory space.

Note: Wrapper for unit-testable address generator to add critical
section and convert bytes to pages.
Note: Free() selects between Free[Alloc] and FreeClaim based on
the address range of the freed address.

Return:     Allocated virtual address if successful (in bytes)
INVALID_VA_GEN_ADDRESS if failed
\* ************************************************************************* */
uint64_t
va_gen_alloc(struct va_gen_addr *addr, uint64_t num_bytes, uint32_t align_bytes)
{
	// Convert input bytes to pages which is our unit for the address generator.
	uint64_t num_pages = (uint64_t)(((PAGE_SIZE - 1) + num_bytes) / PAGE_SIZE);
	uint64_t align_pages = align_bytes / PAGE_SIZE;
	uint64_t va_page_index, ret;

	if (align_bytes < PAGE_SIZE) {
		ret = INVALID_VA_GEN_ADDRESS;
		WARN_ON(1);
		goto done;
	}

	if (num_bytes > (0xffffffffULL * PAGE_SIZE)) {
		ret = INVALID_VA_GEN_ADDRESS;
		WARN_ON(1);
		goto done;
	}
	va_page_index = va_gen_alloc_aligned(addr, num_pages, (uint32_t)(align_pages % 0xffffffff) );

	if (va_page_index == INVALID_VA_PAGE_INDEX)
		return INVALID_VA_GEN_ADDRESS;

	// Convert page number to virtual address, adding base.
	ret = va_page_index << PAGE_SHIFT;
	ret += addr->base;
done:
	return ret;
}

// Claims ownership of a memory region
uint64_t
va_gen_claim(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes)
{
	uint64_t va, num_pages;
	int result;

	if (address + num_bytes > addr->base)
		address = INVALID_VA_GEN_ADDRESS;
	else if (address & (PAGE_SIZE - 1))
		// address not aligned
		address = INVALID_VA_GEN_ADDRESS;
	else {
		va = (uint64_t)(address >> PAGE_SHIFT);
		// pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes);
		// convert input bytes to pages, our unit for the address generator
		num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE);
		if ((result = va_gen_claim_internal(addr, va, num_pages)) < 0)
			address = INVALID_VA_GEN_ADDRESS;
	}
	return address;
}

// frees the address range so the pages may be re-assigned
void
va_gen_free(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes)
{
	uint64_t va, num_pages;

	if (address >= addr->base) {
		// convert virtual address to page number, subtracting base
		address -= addr->base;
		va = (uint64_t)(address >> PAGE_SHIFT);
		// pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes);
		// convert input bytes to pages, our unit for the address generator
		num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE);
		va_gen_free_internal(addr, va, num_pages);
	} else {
		va = (uint64_t)(address >> PAGE_SHIFT);
		// pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes);
		// convert input bytes to pages, our unit for the address generator
		num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE);
		va_gen_free_claim(addr, va, num_pages);
	}
}

// base and range in bytes, though internal va generator works in pages
int
va_gen_init(struct va_gen_addr *addr, uint64_t base, uint64_t range)
{
	uint64_t rangeInPages = (uint64_t)(range >> PAGE_SHIFT);
	int ret;

	if (!(ret = va_gen_init_internal(addr, rangeInPages)))
		addr->base = base;
	return ret;
}

void
va_gen_destroy(struct va_gen_addr *addr)
{
	va_node_destroy(&addr->allocator);
}