Subversion Repositories HelenOS

Rev

Rev 4582 | 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 <malloc.h>
  40. #include <mem.h>
  41. #include <fibril_sync.h>
  42. //#include <stdio.h>
  43. #include <unistd.h>
  44.  
  45. #include <sys/mman.h>
  46.  
  47. #include "../../err.h"
  48.  
  49. #include "../generic_field.h"
  50.  
  51. #include "packet.h"
  52. #include "packet_header.h"
  53.  
  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.      */
  93.     fibril_rwlock_t lock;
  94.     /** Packet map.
  95.      */
  96.     gpm_t   packet_map;
  97. } pm_globals;
  98.  
  99. GENERIC_FIELD_IMPLEMENT( gpm, packet_map_t );
  100.  
  101. int packet_destroy( packet_t packet ){
  102.     if( ! packet_is_valid( packet )) return EINVAL;
  103.     return munmap( packet, packet->length );
  104. }
  105.  
  106. int pm_init( void ){
  107.     ERROR_DECLARE;
  108.  
  109.     fibril_rwlock_initialize( & pm_globals.lock );
  110.     fibril_rwlock_write_lock( & pm_globals.lock );
  111.     ERROR_PROPAGATE( gpm_initialize( & pm_globals.packet_map ));
  112.     fibril_rwlock_write_unlock( & pm_globals.lock );
  113.     return EOK;
  114. }
  115.  
  116. packet_t pm_find( packet_id_t packet_id ){
  117.     packet_map_ref map;
  118.     packet_t packet;
  119.  
  120.     if( ! packet_id ) return NULL;
  121.     fibril_rwlock_read_lock( & pm_globals.lock );
  122.     if( packet_id > PACKET_MAP_SIZE * gpm_count( & pm_globals.packet_map )){
  123.         fibril_rwlock_read_unlock( & pm_globals.lock );
  124.         return NULL;
  125.     }
  126.     map = gpm_get_index( & pm_globals.packet_map, PACKET_MAP_PAGE( packet_id ));
  127.     if( ! map ){
  128.         fibril_rwlock_read_unlock( & pm_globals.lock );
  129.         return NULL;
  130.     }
  131.     packet = ( * map )[ PACKET_MAP_INDEX( packet_id ) ];
  132.     fibril_rwlock_read_unlock( & pm_globals.lock );
  133.     return packet;
  134. }
  135.  
  136. int pm_add( packet_t packet ){
  137.     ERROR_DECLARE;
  138.  
  139.     packet_map_ref map;
  140.  
  141.     if( ! packet_is_valid( packet )) return EINVAL;
  142.     fibril_rwlock_write_lock( & pm_globals.lock );
  143.     if( PACKET_MAP_PAGE( packet->packet_id ) < gpm_count( & pm_globals.packet_map )){
  144.         map = gpm_get_index( & pm_globals.packet_map, PACKET_MAP_PAGE( packet->packet_id ));
  145.     }else{
  146.         do{
  147.             map = ( packet_map_ref ) malloc( sizeof( packet_map_t ));
  148.             if( ! map ){
  149.                 fibril_rwlock_write_unlock( & pm_globals.lock );
  150.                 return ENOMEM;
  151.             }
  152.             bzero( map, sizeof( packet_map_t ));
  153.             if(( ERROR_CODE = gpm_add( & pm_globals.packet_map, map )) < 0 ){
  154.                 fibril_rwlock_write_unlock( & pm_globals.lock );
  155.                 free( map );
  156.                 return ERROR_CODE;
  157.             }
  158.         }while( PACKET_MAP_PAGE( packet->packet_id ) >= gpm_count( & pm_globals.packet_map ));
  159.     }
  160.     ( * map )[ PACKET_MAP_INDEX( packet->packet_id ) ] = packet;
  161.     fibril_rwlock_write_unlock( & pm_globals.lock );
  162.     return EOK;
  163. }
  164.  
  165. void pm_destroy( void ){
  166.     int count;
  167.     int index;
  168.     packet_map_ref map;
  169.     packet_t packet;
  170.  
  171.     fibril_rwlock_write_lock( & pm_globals.lock );
  172.     count = gpm_count( & pm_globals.packet_map );
  173.     while( count > 0 ){
  174.         map = gpm_get_index( & pm_globals.packet_map, count - 1 );
  175.         for( index = PACKET_MAP_SIZE - 1; index >= 0; -- index ){
  176.             packet = ( * map )[ index ];
  177.             if( packet_is_valid( packet )){
  178.                 munmap( packet, packet->length );
  179.             }
  180.         }
  181.     }
  182.     gpm_destroy( & pm_globals.packet_map );
  183.     // leave locked
  184. }
  185.  
  186. packet_t pq_add( packet_t first, packet_t packet, size_t order, size_t metric ){
  187.     packet_t    item;
  188.  
  189.     if( ! packet_is_valid( packet )) return NULL;
  190.     pq_set_order( packet, order, metric );
  191.     if( packet_is_valid( first )){
  192.         item = first;
  193.         do{
  194.             if( item->order < order ){
  195.                 if( item->next ){
  196.                     item = pm_find( item->next );
  197.                 }else{
  198.                     item->next = packet->packet_id;
  199.                     packet->previous = item->packet_id;
  200.                     return first;
  201.                 }
  202.             }else{
  203.                 packet->previous = item->previous;
  204.                 packet->next = item->packet_id;
  205.                 item->previous = packet->packet_id;
  206.                 item = pm_find( packet->previous );
  207.                 if( item ) item->next = packet->packet_id;
  208.                 return item ? first : packet;
  209.             }
  210.         }while( packet_is_valid( item ));
  211.     }
  212.     return packet;
  213. }
  214.  
  215. packet_t pq_find( packet_t packet, size_t order ){
  216.     packet_t    item;
  217.  
  218.     if( ! packet_is_valid( packet )) return NULL;
  219.     if( packet->order == order ) return packet;
  220.     item = pm_find( packet->next );
  221.     while( item && ( item != packet )){
  222.         item = pm_find( item->next );
  223.         if( item->order == order ){
  224.             return item;
  225.         }
  226.     }
  227.     return NULL;
  228. }
  229.  
  230. int pq_insert_after( packet_t packet, packet_t new_packet ){
  231.     packet_t    item;
  232.  
  233.     if( !( packet_is_valid( packet ) && packet_is_valid( new_packet ))) return EINVAL;
  234.     new_packet->previous = packet->packet_id;
  235.     new_packet->next = packet->next;
  236.     item = pm_find( packet->next );
  237.     if( item ) item->previous = new_packet->packet_id;
  238.     packet->next = new_packet->packet_id;
  239.     return EOK;
  240. }
  241.  
  242. packet_t pq_detach( packet_t packet ){
  243.     packet_t next;
  244.     packet_t previous;
  245.  
  246.     if( ! packet_is_valid( packet )) return NULL;
  247.     next = pm_find( packet->next );
  248.     if( next ){
  249.         next->previous = packet->previous;
  250.         previous = pm_find( next->previous );
  251.         if( previous ){
  252.             previous->next = next->packet_id;
  253.         }
  254.     }
  255.     packet->previous = 0;
  256.     packet->next = 0;
  257.     return next;
  258. }
  259.  
  260. int pq_set_order( packet_t packet, size_t order, size_t metric ){
  261.     if( ! packet_is_valid( packet )) return EINVAL;
  262.     packet->order = order;
  263.     packet->metric = metric;
  264.     return EOK;
  265. }
  266.  
  267. int pq_get_order( packet_t packet, size_t * order, size_t * metric ){
  268.     if( ! packet_is_valid( packet )) return EINVAL;
  269.     if( order ) * order = packet->order;
  270.     if( metric ) * metric = packet->metric;
  271.     return EOK;
  272. }
  273.  
  274. void pq_destroy( packet_t first, void ( * packet_release )( packet_t packet )){
  275.     packet_t    actual;
  276.     packet_t    next;
  277.  
  278.     actual = first;
  279.     while( packet_is_valid( actual )){
  280.         next = pm_find( actual->next );
  281.         actual->next = 0;
  282.         actual->previous = 0;
  283.         if( packet_release ) packet_release( actual );
  284.         actual = next;
  285.     }
  286. }
  287.  
  288. packet_t pq_next( packet_t packet ){
  289.     if( ! packet_is_valid( packet )) return NULL;
  290.     return pm_find( packet->next );
  291. }
  292.  
  293. packet_t pq_previous( packet_t packet ){
  294.     if( ! packet_is_valid( packet )) return NULL;
  295.     return pm_find( packet->previous );
  296. }
  297.  
  298. /** @}
  299.  */
  300.