Subversion Repositories test_project

/*

 * Copyright (c) 2006, Intel Corporation.

 *

 * This file is released under the GPLv2.

 *

 * Copyright (C) 2006 Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>

 */

#include "iova.h"

void

init_iova_domain(struct iova_domain *iovad)

{

        spin_lock_init(&iovad->iova_alloc_lock);

        spin_lock_init(&iovad->iova_rbtree_lock);

        iovad->rbroot = RB_ROOT;

        iovad->cached32_node = NULL;

}

static struct rb_node *

__get_cached_rbnode(struct iova_domain *iovad, unsigned long *limit_pfn)

{

        if ((*limit_pfn != DMA_32BIT_PFN) ||

                (iovad->cached32_node == NULL))

                return rb_last(&iovad->rbroot);

        else {

                struct rb_node *prev_node = rb_prev(iovad->cached32_node);

                struct iova *curr_iova =

                        container_of(iovad->cached32_node, struct iova, node);

                *limit_pfn = curr_iova->pfn_lo - 1;

                return prev_node;

        }

}

static void

__cached_rbnode_insert_update(struct iova_domain *iovad,

        unsigned long limit_pfn, struct iova *new)

{

        if (limit_pfn != DMA_32BIT_PFN)

                return;

        iovad->cached32_node = &new->node;

}

static void

__cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)

{

        struct iova *cached_iova;

        struct rb_node *curr;

        if (!iovad->cached32_node)

                return;

        curr = iovad->cached32_node;

        cached_iova = container_of(curr, struct iova, node);

        if (free->pfn_lo >= cached_iova->pfn_lo)

                iovad->cached32_node = rb_next(&free->node);

}

/* Computes the padding size required, to make the

 * the start address naturally aligned on its size

 */

static int

iova_get_pad_size(int size, unsigned int limit_pfn)

{

        unsigned int pad_size = 0;

        unsigned int order = ilog2(size);

        if (order)

                pad_size = (limit_pfn + 1) % (1 << order);

        return pad_size;

}

static int __alloc_iova_range(struct iova_domain *iovad, unsigned long size,

                unsigned long limit_pfn, struct iova *new, bool size_aligned)

{

        struct rb_node *curr = NULL;

        unsigned long flags;

        unsigned long saved_pfn;

        unsigned int pad_size = 0;

        /* Walk the tree backwards */

        spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

        saved_pfn = limit_pfn;

        curr = __get_cached_rbnode(iovad, &limit_pfn);

        while (curr) {

                struct iova *curr_iova = container_of(curr, struct iova, node);

                if (limit_pfn < curr_iova->pfn_lo)

                        goto move_left;

                else if (limit_pfn < curr_iova->pfn_hi)

                        goto adjust_limit_pfn;

                else {

                        if (size_aligned)

                                pad_size = iova_get_pad_size(size, limit_pfn);

                        if ((curr_iova->pfn_hi + size + pad_size) <= limit_pfn)

                                break;  /* found a free slot */

                }

adjust_limit_pfn:

                limit_pfn = curr_iova->pfn_lo - 1;

move_left:

                curr = rb_prev(curr);

        }

        if (!curr) {

                if (size_aligned)

                        pad_size = iova_get_pad_size(size, limit_pfn);

                if ((IOVA_START_PFN + size + pad_size) > limit_pfn) {

                        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

                        return -ENOMEM;

                }

        }

        /* pfn_lo will point to size aligned address if size_aligned is set */

        new->pfn_lo = limit_pfn - (size + pad_size) + 1;

        new->pfn_hi = new->pfn_lo + size - 1;

        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

        return 0;

}

static void

iova_insert_rbtree(struct rb_root *root, struct iova *iova)

{

        struct rb_node **new = &(root->rb_node), *parent = NULL;

        /* Figure out where to put new node */

        while (*new) {

                struct iova *this = container_of(*new, struct iova, node);

                parent = *new;

                if (iova->pfn_lo < this->pfn_lo)

                        new = &((*new)->rb_left);

                else if (iova->pfn_lo > this->pfn_lo)

                        new = &((*new)->rb_right);

                else

                        BUG(); /* this should not happen */

        }

        /* Add new node and rebalance tree. */

        rb_link_node(&iova->node, parent, new);

        rb_insert_color(&iova->node, root);

}

/**

 * alloc_iova - allocates an iova

 * @iovad - iova domain in question

 * @size - size of page frames to allocate

 * @limit_pfn - max limit address

 * @size_aligned - set if size_aligned address range is required

 * This function allocates an iova in the range limit_pfn to IOVA_START_PFN

 * looking from limit_pfn instead from IOVA_START_PFN. If the size_aligned

 * flag is set then the allocated address iova->pfn_lo will be naturally

 * aligned on roundup_power_of_two(size).

 */

struct iova *

alloc_iova(struct iova_domain *iovad, unsigned long size,

        unsigned long limit_pfn,

        bool size_aligned)

{

        unsigned long flags;

        struct iova *new_iova;

        int ret;

        new_iova = alloc_iova_mem();

        if (!new_iova)

                return NULL;

        /* If size aligned is set then round the size to

         * to next power of two.

         */

        if (size_aligned)

                size = __roundup_pow_of_two(size);

        spin_lock_irqsave(&iovad->iova_alloc_lock, flags);

        ret = __alloc_iova_range(iovad, size, limit_pfn, new_iova,

                        size_aligned);

        if (ret) {

                spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);

                free_iova_mem(new_iova);

                return NULL;

        }

        /* Insert the new_iova into domain rbtree by holding writer lock */

        spin_lock(&iovad->iova_rbtree_lock);

        iova_insert_rbtree(&iovad->rbroot, new_iova);

        __cached_rbnode_insert_update(iovad, limit_pfn, new_iova);

        spin_unlock(&iovad->iova_rbtree_lock);

        spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);

        return new_iova;

}

/**

 * find_iova - find's an iova for a given pfn

 * @iovad - iova domain in question.

 * pfn - page frame number

 * This function finds and returns an iova belonging to the

 * given doamin which matches the given pfn.

 */

struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)

{

        unsigned long flags;

        struct rb_node *node;

        /* Take the lock so that no other thread is manipulating the rbtree */

        spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

        node = iovad->rbroot.rb_node;

        while (node) {

                struct iova *iova = container_of(node, struct iova, node);

                /* If pfn falls within iova's range, return iova */

                if ((pfn >= iova->pfn_lo) && (pfn <= iova->pfn_hi)) {

                        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

                        /* We are not holding the lock while this iova

                         * is referenced by the caller as the same thread

                         * which called this function also calls __free_iova()

                         * and it is by desing that only one thread can possibly

                         * reference a particular iova and hence no conflict.

                         */

                        return iova;

                }

                if (pfn < iova->pfn_lo)

                        node = node->rb_left;

                else if (pfn > iova->pfn_lo)

                        node = node->rb_right;

        }

        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

        return NULL;

}

/**

 * __free_iova - frees the given iova

 * @iovad: iova domain in question.

 * @iova: iova in question.

 * Frees the given iova belonging to the giving domain

 */

void

__free_iova(struct iova_domain *iovad, struct iova *iova)

{

        unsigned long flags;

        spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

        __cached_rbnode_delete_update(iovad, iova);

        rb_erase(&iova->node, &iovad->rbroot);

        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

        free_iova_mem(iova);

}

/**

 * free_iova - finds and frees the iova for a given pfn

 * @iovad: - iova domain in question.

 * @pfn: - pfn that is allocated previously

 * This functions finds an iova for a given pfn and then

 * frees the iova from that domain.

 */

void

free_iova(struct iova_domain *iovad, unsigned long pfn)

{

        struct iova *iova = find_iova(iovad, pfn);

        if (iova)

                __free_iova(iovad, iova);

}

/**

 * put_iova_domain - destroys the iova doamin

 * @iovad: - iova domain in question.

 * All the iova's in that domain are destroyed.

 */

void put_iova_domain(struct iova_domain *iovad)

{

        struct rb_node *node;

        unsigned long flags;

        spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

        node = rb_first(&iovad->rbroot);

        while (node) {

                struct iova *iova = container_of(node, struct iova, node);

                rb_erase(node, &iovad->rbroot);

                free_iova_mem(iova);

                node = rb_first(&iovad->rbroot);

        }

        spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

}

static int

__is_range_overlap(struct rb_node *node,

        unsigned long pfn_lo, unsigned long pfn_hi)

{

        struct iova *iova = container_of(node, struct iova, node);

        if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))

                return 1;

        return 0;

}

static struct iova *

__insert_new_range(struct iova_domain *iovad,

        unsigned long pfn_lo, unsigned long pfn_hi)

{

        struct iova *iova;

        iova = alloc_iova_mem();

        if (!iova)

                return iova;

        iova->pfn_hi = pfn_hi;

        iova->pfn_lo = pfn_lo;

        iova_insert_rbtree(&iovad->rbroot, iova);

        return iova;

}

static void

__adjust_overlap_range(struct iova *iova,

        unsigned long *pfn_lo, unsigned long *pfn_hi)

{

        if (*pfn_lo < iova->pfn_lo)

                iova->pfn_lo = *pfn_lo;

        if (*pfn_hi > iova->pfn_hi)

                *pfn_lo = iova->pfn_hi + 1;

}

/**

 * reserve_iova - reserves an iova in the given range

 * @iovad: - iova domain pointer

 * @pfn_lo: - lower page frame address

 * @pfn_hi:- higher pfn adderss

 * This function allocates reserves the address range from pfn_lo to pfn_hi so

 * that this address is not dished out as part of alloc_iova.

 */

struct iova *

reserve_iova(struct iova_domain *iovad,

        unsigned long pfn_lo, unsigned long pfn_hi)

{

        struct rb_node *node;

        unsigned long flags;

        struct iova *iova;

        unsigned int overlap = 0;

        spin_lock_irqsave(&iovad->iova_alloc_lock, flags);

        spin_lock(&iovad->iova_rbtree_lock);

        for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {

                if (__is_range_overlap(node, pfn_lo, pfn_hi)) {

                        iova = container_of(node, struct iova, node);

                        __adjust_overlap_range(iova, &pfn_lo, &pfn_hi);

                        if ((pfn_lo >= iova->pfn_lo) &&

                                (pfn_hi <= iova->pfn_hi))

                                goto finish;

                        overlap = 1;

                } else if (overlap)

                                break;

        }

        /* We are here either becasue this is the first reserver node

         * or need to insert remaining non overlap addr range

         */

        iova = __insert_new_range(iovad, pfn_lo, pfn_hi);

finish:

        spin_unlock(&iovad->iova_rbtree_lock);

        spin_unlock_irqrestore(&iovad->iova_alloc_lock, flags);

        return iova;

}

/**

 * copy_reserved_iova - copies the reserved between domains

 * @from: - source doamin from where to copy

 * @to: - destination domin where to copy

 * This function copies reserved iova's from one doamin to

 * other.

 */

void

copy_reserved_iova(struct iova_domain *from, struct iova_domain *to)

{

        unsigned long flags;

        struct rb_node *node;

        spin_lock_irqsave(&from->iova_alloc_lock, flags);

        spin_lock(&from->iova_rbtree_lock);

        for (node = rb_first(&from->rbroot); node; node = rb_next(node)) {

                struct iova *iova = container_of(node, struct iova, node);

                struct iova *new_iova;

                new_iova = reserve_iova(to, iova->pfn_lo, iova->pfn_hi);

                if (!new_iova)

                        printk(KERN_ERR "Reserve iova range %lx@%lx failed\n",

                                iova->pfn_lo, iova->pfn_lo);

        }

        spin_unlock(&from->iova_rbtree_lock);

        spin_unlock_irqrestore(&from->iova_alloc_lock, flags);

}