source: mainline/uspace/lib/c/generic/net/packet.c@ b402dadd

/*
 * Copyright (c) 2009 Lukas Mejdrech
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup libc
 *  @{
 */

/** @file
 *  Packet map and queue implementation.
 *  This file has to be compiled with both the packet server and the client.
 */

#include <assert.h>
#include <malloc.h>
#include <mem.h>
#include <fibril_synch.h>
#include <unistd.h>
#include <errno.h>

#include <sys/mman.h>

#include <adt/hash_table.h>
#include <net/packet.h>
#include <net/packet_header.h>

/** Packet hash table size. */
#define PACKET_HASH_TABLE_SIZE  128

/** Packet map global data. */
static struct {
        /** Safety lock. */
        fibril_rwlock_t lock;
        /** Packet map. */
        hash_table_t packet_map;
        /** Packet map operations */
        hash_table_operations_t operations;
} pm_globals;

typedef struct {
        link_t link;
        packet_t *packet;
} pm_entry_t;

/**
 * Hash function for the packet mapping hash table
 */
static hash_index_t pm_hash(unsigned long key[])
{
        return (hash_index_t) key[0] % PACKET_HASH_TABLE_SIZE;
}

/**
 * Key compare function for the packet mapping hash table
 */
static int pm_compare(unsigned long key[], hash_count_t keys, link_t *link)
{
        pm_entry_t *entry = list_get_instance(link, pm_entry_t, link);
        return entry->packet->packet_id == key[0];
}

/**
 * Remove callback for the packet mapping hash table
 */
static void pm_remove_callback(link_t *link)
{
        pm_entry_t *entry = list_get_instance(link, pm_entry_t, link);
        free(entry);
}

/**
 * Wrapper used when destroying the whole table
 */
static void pm_free_wrapper(link_t *link, void *ignored)
{
        pm_entry_t *entry = list_get_instance(link, pm_entry_t, link);
        free(entry);
}


/** Initializes the packet map.
 *
 * @return              EOK on success.
 * @return              ENOMEM if there is not enough memory left.
 */
int pm_init(void)
{
        int rc = EOK;

        fibril_rwlock_initialize(&pm_globals.lock);
        
        fibril_rwlock_write_lock(&pm_globals.lock);
        
        pm_globals.operations.hash = pm_hash;
        pm_globals.operations.compare = pm_compare;
        pm_globals.operations.remove_callback = pm_remove_callback;

        if (!hash_table_create(&pm_globals.packet_map, PACKET_HASH_TABLE_SIZE, 1,
            &pm_globals.operations))
                rc = ENOMEM;
        
        fibril_rwlock_write_unlock(&pm_globals.lock);
        
        return rc;
}

/** Finds the packet mapping.
 *
 * @param[in] packet_id Packet identifier to be found.
 *
 * @return The found packet reference.
 * @return NULL if the mapping does not exist.
 *
 */
packet_t *pm_find(packet_id_t packet_id)
{
        if (!packet_id)
                return NULL;
        
        fibril_rwlock_read_lock(&pm_globals.lock);
        
        unsigned long key = packet_id;
        link_t *link = hash_table_find(&pm_globals.packet_map, &key);
        
        packet_t *packet;
        if (link != NULL) {
                pm_entry_t *entry =
                    hash_table_get_instance(link, pm_entry_t, link);
                packet = entry->packet;
        } else
                packet = NULL;
        
        fibril_rwlock_read_unlock(&pm_globals.lock);
        return packet;
}

/** Adds the packet mapping.
 *
 * @param[in] packet Packet to be remembered.
 *
 * @return EOK on success.
 * @return EINVAL if the packet is not valid.
 * @return ENOMEM if there is not enough memory left.
 *
 */
int pm_add(packet_t *packet)
{
        if (!packet_is_valid(packet))
                return EINVAL;
        
        fibril_rwlock_write_lock(&pm_globals.lock);
        
        pm_entry_t *entry = malloc(sizeof(pm_entry_t));
        if (entry == NULL) {
                fibril_rwlock_write_unlock(&pm_globals.lock);
                return ENOMEM;
        }
        
        entry->packet = packet;
        
        unsigned long key = packet->packet_id;
        hash_table_insert(&pm_globals.packet_map, &key, &entry->link);
        
        fibril_rwlock_write_unlock(&pm_globals.lock);
        
        return EOK;
}

/** Remove the packet mapping
 *
 * @param[in] packet The packet to be removed
 *
 */
void pm_remove(packet_t *packet)
{
        assert(packet_is_valid(packet));
        
        fibril_rwlock_write_lock(&pm_globals.lock);
        
        unsigned long key = packet->packet_id;
        hash_table_remove(&pm_globals.packet_map, &key, 1);
        
        fibril_rwlock_write_unlock(&pm_globals.lock);
}

/** Release the packet map. */
void pm_destroy(void)
{
        fibril_rwlock_write_lock(&pm_globals.lock);
        hash_table_apply(&pm_globals.packet_map, pm_free_wrapper, NULL);
        hash_table_destroy(&pm_globals.packet_map);
        /* Leave locked */
}

/** Add packet to the sorted queue.
 *
 * The queue is sorted in the ascending order.
 * The packet is inserted right before the packets of the same order value.
 *
 * @param[in,out] first First packet of the queue. Sets the first
 *                      packet of the queue. The original first packet
 *                      may be shifted by the new packet.
 * @param[in] packet    Packet to be added.
 * @param[in] order     Packet order value.
 * @param[in] metric    Metric value of the packet.
 *
 * @return EOK on success.
 * @return EINVAL if the first parameter is NULL.
 * @return EINVAL if the packet is not valid.
 *
 */
int pq_add(packet_t **first, packet_t *packet, size_t order, size_t metric)
{
        if ((!first) || (!packet_is_valid(packet)))
                return EINVAL;
        
        pq_set_order(packet, order, metric);
        if (packet_is_valid(*first)) {
                packet_t *cur = *first;
                
                do {
                        if (cur->order < order) {
                                if (cur->next)
                                        cur = pm_find(cur->next);
                                else {
                                        cur->next = packet->packet_id;
                                        packet->previous = cur->packet_id;
                                        
                                        return EOK;
                                }
                        } else {
                                packet->previous = cur->previous;
                                packet->next = cur->packet_id;
                                
                                cur->previous = packet->packet_id;
                                cur = pm_find(packet->previous);
                                
                                if (cur)
                                        cur->next = packet->packet_id;
                                else
                                        *first = packet;
                                
                                return EOK;
                        }
                } while (packet_is_valid(cur));
        }
        
        *first = packet;
        return EOK;
}

/** Finds the packet with the given order.
 *
 * @param[in] first     The first packet of the queue.
 * @param[in] order     The packet order value.
 * @return              The packet with the given order.
 * @return              NULL if the first packet is not valid.
 * @return              NULL if the packet is not found.
 */
packet_t *pq_find(packet_t *packet, size_t order)
{
        packet_t *item;

        if (!packet_is_valid(packet))
                return NULL;

        item = packet;
        do {
                if (item->order == order)
                        return item;

                item = pm_find(item->next);
        } while (item && (item != packet) && packet_is_valid(item));

        return NULL;
}

/** Inserts packet after the given one.
 *
 * @param[in] packet    The packet in the queue.
 * @param[in] new_packet The new packet to be inserted.
 * @return              EOK on success.
 * @return              EINVAL if etiher of the packets is invalid.
 */
int pq_insert_after(packet_t *packet, packet_t *new_packet)
{
        packet_t *item;

        if (!packet_is_valid(packet) || !packet_is_valid(new_packet))
                return EINVAL;

        new_packet->previous = packet->packet_id;
        new_packet->next = packet->next;
        item = pm_find(packet->next);
        if (item)
                item->previous = new_packet->packet_id;
        packet->next = new_packet->packet_id;

        return EOK;
}

/** Detach the packet from the queue.
 *
 * @param[in] packet    The packet to be detached.
 * @return              The next packet in the queue. If the packet is the first
 *                      one of the queue, this becomes the new first one.
 * @return              NULL if there is no packet left.
 * @return              NULL if the packet is not valid.
 */
packet_t *pq_detach(packet_t *packet)
{
        packet_t *next;
        packet_t *previous;

        if (!packet_is_valid(packet))
                return NULL;

        next = pm_find(packet->next);
        if (next)
                next->previous = packet->previous;
        
        previous = pm_find(packet->previous);
        if (previous)
                previous->next = packet->next ;
        
        packet->previous = 0;
        packet->next = 0;
        return next;
}

/** Sets the packet order and metric attributes.
 *
 * @param[in] packeti   The packet to be set.
 * @param[in] order     The packet order value.
 * @param[in] metric    The metric value of the packet.
 * @return              EOK on success.
 * @return              EINVAL if the packet is invalid.
 */
int pq_set_order(packet_t *packet, size_t order, size_t metric)
{
        if (!packet_is_valid(packet))
                return EINVAL;

        packet->order = order;
        packet->metric = metric;
        return EOK;
}

/** Sets the packet order and metric attributes.
 *
 * @param[in] packet    The packet to be set.
 * @param[out] order    The packet order value.
 * @param[out] metric   The metric value of the packet.
 * @return              EOK on success.
 * @return              EINVAL if the packet is invalid.
 */
int pq_get_order(packet_t *packet, size_t *order, size_t *metric)
{
        if (!packet_is_valid(packet))
                return EINVAL;

        if (order)
                *order = packet->order;

        if (metric)
                *metric = packet->metric;

        return EOK;
}

/** Releases the whole queue.
 *
 * Detaches all packets of the queue and calls the packet_release() for each of
 * them.
 *
 * @param[in] first     The first packet of the queue.
 * @param[in] packet_release The releasing function called for each of the
 *                      packets after its detachment.
 */
void pq_destroy(packet_t *first, void (*packet_release)(packet_t *packet))
{
        packet_t *actual;
        packet_t *next;

        actual = first;
        while (packet_is_valid(actual)) {
                next = pm_find(actual->next);
                actual->next = 0;
                actual->previous = 0;
                if(packet_release)
                        packet_release(actual);
                actual = next;
        }
}

/** Returns the next packet in the queue.
 *
 * @param[in] packet    The packet queue member.
 * @return              The next packet in the queue.
 * @return              NULL if there is no next packet.
 * @return              NULL if the packet is not valid.
 */
packet_t *pq_next(packet_t *packet)
{
        if (!packet_is_valid(packet))
                return NULL;

        return pm_find(packet->next);
}

/** Returns the previous packet in the queue.
 *
 * @param[in] packet    The packet queue member.
 * @return              The previous packet in the queue.
 * @return              NULL if there is no previous packet.
 * @return              NULL if the packet is not valid.
 */
packet_t *pq_previous(packet_t *packet)
{
        if (!packet_is_valid(packet))
                return NULL;

        return pm_find(packet->previous);
}

/** @}
 */