Subversion Repositories HelenOS

Rev

Rev 3912 | Rev 4075 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2009 Lukas Mejdrech
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup packet
  30.  *  @{
  31.  */
  32.  
  33. /** @file
  34.  *  Packet map and queue implementation.
  35.  *  This file has to be compiled with both the packet server and the client.
  36.  */
  37.  
  38. #include <errno.h>
  39. #include <futex.h>
  40. #include <malloc.h>
  41. //#include <stdio.h>
  42. #include <string.h>
  43.  
  44. #include <sys/mman.h>
  45.  
  46. #include "../../err.h"
  47.  
  48. #include "../generic_field.h"
  49.  
  50. #include "packet_header.h"
  51. #include "packet.h"
  52.  
  53. // TODO power of 2 aritmetic => div and mod speedup?
  54. /** Packet map page size.
  55.  */
  56. #define PACKET_MAP_SIZE 100
  57.  
  58. /** Returns the packet map page index.
  59.  *  @param packet_id The packet identifier.
  60.  */
  61. #define PACKET_MAP_PAGE( packet_id )    ((( packet_id ) - 1 ) / PACKET_MAP_SIZE )
  62.  
  63. /** Returns the packet index in the corresponding packet map page.
  64.  *  @param packet_id The packet identifier.
  65.  */
  66. #define PACKET_MAP_INDEX( packet_id )   ((( packet_id ) - 1 ) % PACKET_MAP_SIZE )
  67.  
  68. /** Type definition of the packet map page.
  69.  */
  70. typedef packet_t packet_map_t[ PACKET_MAP_SIZE ];
  71. /** Type definition of the packet map page pointer.
  72.  */
  73. typedef packet_map_t * packet_map_ref;
  74.  
  75. /** Packet map.
  76.  *  Maps packet identifiers to the packet references.
  77.  *  @see generic_field.h
  78.  */
  79. GENERIC_FIELD_DECLARE( gpm, packet_map_t );
  80.  
  81. /** Releases the packet.
  82.  *  @param packet The packet to be released. Input parameter.
  83.  *  @returns EOK on success.
  84.  *  @returns EINVAL if the packet is not valid.
  85.  */
  86. int packet_destroy( packet_t packet );
  87.  
  88. /** Packet map global data.
  89.  */
  90. static struct{
  91.     /** Safety lock.
  92.      *  Used as a&nbsp;mutex.
  93.      */
  94.     futex_t lock;
  95.     /** Packet map.
  96.      */
  97.     gpm_t   packet_map;
  98. } pm_globals;
  99.  
  100. GENERIC_FIELD_IMPLEMENT( gpm, packet_map_t );
  101.  
  102. int packet_destroy( packet_t packet ){
  103.     if( ! packet_is_valid( packet )) return EINVAL;
  104.     return munmap( packet, packet->length );
  105. }
  106.  
  107. int pm_init( void ){
  108.     ERROR_DECLARE;
  109.  
  110.     // start locked
  111.     futex_initialize( & pm_globals.lock, 0 );
  112.     ERROR_PROPAGATE( gpm_initialize( & pm_globals.packet_map ));
  113.     // release the lock
  114.     futex_up( & pm_globals.lock );
  115.     return EOK;
  116. }
  117.  
  118. packet_t pm_find( packet_id_t packet_id ){
  119.     packet_map_ref map;
  120.     packet_t packet;
  121.  
  122.     if( ! packet_id ) return NULL;
  123.     futex_down( & pm_globals.lock );
  124.     if( packet_id > PACKET_MAP_SIZE * gpm_count( & pm_globals.packet_map )){
  125.         futex_up( & pm_globals.lock );
  126.         return NULL;
  127.     }
  128.     map = gpm_get_index( & pm_globals.packet_map, PACKET_MAP_PAGE( packet_id ));
  129.     if( ! map ){
  130.         futex_up( & pm_globals.lock );
  131.         return NULL;
  132.     }
  133.     packet = ( * map )[ PACKET_MAP_INDEX( packet_id ) ];
  134.     futex_up( & pm_globals.lock );
  135.     return packet;
  136. }
  137.  
  138. int pm_add( packet_t packet ){
  139.     ERROR_DECLARE;
  140.  
  141.     packet_map_ref map;
  142.  
  143.     if( ! packet_is_valid( packet )) return EINVAL;
  144.     futex_down( & pm_globals.lock );
  145.     if( PACKET_MAP_PAGE( packet->packet_id ) < gpm_count( & pm_globals.packet_map )){
  146.         map = gpm_get_index( & pm_globals.packet_map, PACKET_MAP_PAGE( packet->packet_id ));
  147.     }else{
  148.         do{
  149.             map = ( packet_map_ref ) malloc( sizeof( packet_map_t ));
  150.             if( ! map ){
  151.                 futex_up( & pm_globals.lock );
  152.                 return ENOMEM;
  153.             }
  154.             memset( map, 0, sizeof( packet_map_t ));
  155.             if(( ERROR_CODE = gpm_add( & pm_globals.packet_map, map )) < 0 ){
  156.                 free( map );
  157.                 futex_up( & pm_globals.lock );
  158.                 return ERROR_CODE;
  159.             }
  160.         }while( PACKET_MAP_PAGE( packet->packet_id ) >= gpm_count( & pm_globals.packet_map ));
  161.     }
  162.     ( * map )[ PACKET_MAP_INDEX( packet->packet_id ) ] = packet;
  163.     futex_up( & pm_globals.lock );
  164.     return EOK;
  165. }
  166.  
  167. void pm_destroy( void ){
  168.     int count;
  169.     int index;
  170.     packet_map_ref map;
  171.     packet_t packet;
  172.  
  173.     futex_down( & pm_globals.lock );
  174.     count = gpm_count( & pm_globals.packet_map );
  175.     while( count > 0 ){
  176.         map = gpm_get_index( & pm_globals.packet_map, count - 1 );
  177.         for( index = PACKET_MAP_SIZE - 1; index >= 0; -- index ){
  178.             packet = ( * map )[ index ];
  179.             if( packet_is_valid( packet )){
  180.                 munmap( packet, packet->length );
  181.             }
  182.         }
  183.     }
  184.     gpm_destroy( & pm_globals.packet_map );
  185.     // leave locked
  186. }
  187.  
  188. packet_t pq_add( packet_t first, packet_t packet, int order, size_t metric ){
  189.     packet_t    item;
  190.  
  191.     if( ! packet_is_valid( packet )) return NULL;
  192.     pq_set( packet, order, metric );
  193.     if( packet_is_valid( first )){
  194.         item = first;
  195.         do{
  196.             if( item->order < order ){
  197.                 if( item->next ){
  198.                     item = pm_find( item->next );
  199.                 }else{
  200.                     item->next = packet->packet_id;
  201.                     packet->previous = item->packet_id;
  202.                     return first;
  203.                 }
  204.             }else{
  205.                 packet->previous = item->previous;
  206.                 packet->next = item->packet_id;
  207.                 item->previous = packet->packet_id;
  208.                 item = pm_find( packet->previous );
  209.                 if( item ) item->next = packet->packet_id;
  210.                 return item;
  211.             }
  212.         }while( packet_is_valid( item ));
  213.     }
  214.     return packet;
  215. }
  216.  
  217. packet_t pq_detach( packet_t packet ){
  218.     packet_t next;
  219.     packet_t previous;
  220.  
  221.     if( ! packet_is_valid( packet )) return NULL;
  222.     next = pm_find( packet->next );
  223.     if( next ){
  224.         next->previous = packet->previous;
  225.         previous = pm_find( next->previous );
  226.         if( previous ){
  227.             previous->next = next->packet_id;
  228.         }
  229.     }
  230.     packet->previous = 0;
  231.     packet->next = 0;
  232.     return next;
  233. }
  234.  
  235. int pq_set( packet_t packet, int order, size_t metric ){
  236.     if( ! packet_is_valid( packet )) return EINVAL;
  237.     packet->order = order;
  238.     packet->metric = metric;
  239.     return EOK;
  240. }
  241.  
  242. void pq_destroy( packet_t first, void ( * packet_release )( packet_t packet )){
  243.     packet_t    actual;
  244.     packet_t    next;
  245.  
  246.     actual = first;
  247.     while( packet_is_valid( actual )){
  248.         next = pm_find( actual->next );
  249.         actual->next = 0;
  250.         actual->previous = 0;
  251.         if( packet_release ) packet_release( actual );
  252.         actual = next;
  253.     }
  254. }
  255.  
  256. /** @}
  257.  */
  258.