Rev 4731 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
3886 | mejdrech | 1 | /* |
3912 | mejdrech | 2 | * Copyright (c) 2009 Lukas Mejdrech |
3886 | 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 | |||
3912 | mejdrech | 29 | /** @addtogroup packet |
3901 | mejdrech | 30 | * @{ |
3886 | mejdrech | 31 | */ |
32 | |||
33 | /** @file |
||
3912 | mejdrech | 34 | * Packet map and queue implementation. |
35 | * This file has to be compiled with both the packet server and the client. |
||
3886 | mejdrech | 36 | */ |
37 | |||
38 | #include <errno.h> |
||
3901 | mejdrech | 39 | #include <malloc.h> |
4192 | mejdrech | 40 | #include <mem.h> |
4582 | mejdrech | 41 | #include <fibril_sync.h> |
3901 | mejdrech | 42 | //#include <stdio.h> |
4505 | mejdrech | 43 | #include <unistd.h> |
3886 | mejdrech | 44 | |
45 | #include <sys/mman.h> |
||
46 | |||
47 | #include "../../err.h" |
||
48 | |||
3901 | mejdrech | 49 | #include "../generic_field.h" |
50 | |||
4505 | mejdrech | 51 | #include "packet.h" |
3901 | mejdrech | 52 | #include "packet_header.h" |
3886 | mejdrech | 53 | |
3912 | mejdrech | 54 | /** Packet map page size. |
55 | */ |
||
3901 | mejdrech | 56 | #define PACKET_MAP_SIZE 100 |
3886 | mejdrech | 57 | |
3912 | mejdrech | 58 | /** Returns the packet map page index. |
4756 | mejdrech | 59 | * @param[in] packet_id The packet identifier. |
3912 | mejdrech | 60 | */ |
3901 | mejdrech | 61 | #define PACKET_MAP_PAGE( packet_id ) ((( packet_id ) - 1 ) / PACKET_MAP_SIZE ) |
3912 | mejdrech | 62 | |
63 | /** Returns the packet index in the corresponding packet map page. |
||
4756 | mejdrech | 64 | * @param[in] packet_id The packet identifier. |
3912 | mejdrech | 65 | */ |
3901 | mejdrech | 66 | #define PACKET_MAP_INDEX( packet_id ) ((( packet_id ) - 1 ) % PACKET_MAP_SIZE ) |
3886 | mejdrech | 67 | |
3912 | mejdrech | 68 | /** Type definition of the packet map page. |
69 | */ |
||
3901 | mejdrech | 70 | typedef packet_t packet_map_t[ PACKET_MAP_SIZE ]; |
3912 | mejdrech | 71 | /** Type definition of the packet map page pointer. |
72 | */ |
||
3901 | mejdrech | 73 | typedef packet_map_t * packet_map_ref; |
74 | |||
3912 | mejdrech | 75 | /** Packet map. |
76 | * Maps packet identifiers to the packet references. |
||
77 | * @see generic_field.h |
||
78 | */ |
||
3901 | mejdrech | 79 | GENERIC_FIELD_DECLARE( gpm, packet_map_t ); |
80 | |||
3912 | mejdrech | 81 | /** Releases the packet. |
4756 | mejdrech | 82 | * @param[in] packet The packet to be released. |
3912 | mejdrech | 83 | * @returns EOK on success. |
84 | * @returns EINVAL if the packet is not valid. |
||
85 | */ |
||
86 | int packet_destroy( packet_t packet ); |
||
3901 | mejdrech | 87 | |
3912 | mejdrech | 88 | /** Packet map global data. |
89 | */ |
||
3901 | mejdrech | 90 | static struct{ |
3914 | mejdrech | 91 | /** Safety lock. |
92 | */ |
||
4582 | mejdrech | 93 | fibril_rwlock_t lock; |
3912 | mejdrech | 94 | /** Packet map. |
95 | */ |
||
3914 | mejdrech | 96 | gpm_t packet_map; |
3901 | mejdrech | 97 | } pm_globals; |
98 | |||
3912 | mejdrech | 99 | GENERIC_FIELD_IMPLEMENT( gpm, packet_map_t ); |
100 | |||
3901 | mejdrech | 101 | int packet_destroy( packet_t packet ){ |
102 | if( ! packet_is_valid( packet )) return EINVAL; |
||
103 | return munmap( packet, packet->length ); |
||
3886 | mejdrech | 104 | } |
105 | |||
3901 | mejdrech | 106 | int pm_init( void ){ |
3914 | mejdrech | 107 | ERROR_DECLARE; |
108 | |||
4582 | mejdrech | 109 | fibril_rwlock_initialize( & pm_globals.lock ); |
110 | fibril_rwlock_write_lock( & pm_globals.lock ); |
||
3914 | mejdrech | 111 | ERROR_PROPAGATE( gpm_initialize( & pm_globals.packet_map )); |
4582 | mejdrech | 112 | fibril_rwlock_write_unlock( & pm_globals.lock ); |
3914 | mejdrech | 113 | return EOK; |
3886 | mejdrech | 114 | } |
115 | |||
3901 | mejdrech | 116 | packet_t pm_find( packet_id_t packet_id ){ |
117 | packet_map_ref map; |
||
3914 | mejdrech | 118 | packet_t packet; |
3886 | mejdrech | 119 | |
3901 | mejdrech | 120 | if( ! packet_id ) return NULL; |
4582 | mejdrech | 121 | fibril_rwlock_read_lock( & pm_globals.lock ); |
3914 | mejdrech | 122 | if( packet_id > PACKET_MAP_SIZE * gpm_count( & pm_globals.packet_map )){ |
4582 | mejdrech | 123 | fibril_rwlock_read_unlock( & pm_globals.lock ); |
3914 | mejdrech | 124 | return NULL; |
125 | } |
||
3912 | mejdrech | 126 | map = gpm_get_index( & pm_globals.packet_map, PACKET_MAP_PAGE( packet_id )); |
3914 | mejdrech | 127 | if( ! map ){ |
4582 | mejdrech | 128 | fibril_rwlock_read_unlock( & pm_globals.lock ); |
3914 | mejdrech | 129 | return NULL; |
130 | } |
||
131 | packet = ( * map )[ PACKET_MAP_INDEX( packet_id ) ]; |
||
4582 | mejdrech | 132 | fibril_rwlock_read_unlock( & pm_globals.lock ); |
3914 | mejdrech | 133 | return packet; |
3886 | mejdrech | 134 | } |
135 | |||
3901 | mejdrech | 136 | int pm_add( packet_t packet ){ |
137 | ERROR_DECLARE; |
||
138 | |||
139 | packet_map_ref map; |
||
140 | |||
3914 | mejdrech | 141 | if( ! packet_is_valid( packet )) return EINVAL; |
4582 | mejdrech | 142 | fibril_rwlock_write_lock( & pm_globals.lock ); |
3912 | mejdrech | 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 )); |
||
3901 | mejdrech | 145 | }else{ |
146 | do{ |
||
147 | map = ( packet_map_ref ) malloc( sizeof( packet_map_t )); |
||
3914 | mejdrech | 148 | if( ! map ){ |
4582 | mejdrech | 149 | fibril_rwlock_write_unlock( & pm_globals.lock ); |
3914 | mejdrech | 150 | return ENOMEM; |
151 | } |
||
4192 | mejdrech | 152 | bzero( map, sizeof( packet_map_t )); |
3912 | mejdrech | 153 | if(( ERROR_CODE = gpm_add( & pm_globals.packet_map, map )) < 0 ){ |
4582 | mejdrech | 154 | fibril_rwlock_write_unlock( & pm_globals.lock ); |
3901 | mejdrech | 155 | free( map ); |
156 | return ERROR_CODE; |
||
157 | } |
||
3912 | mejdrech | 158 | }while( PACKET_MAP_PAGE( packet->packet_id ) >= gpm_count( & pm_globals.packet_map )); |
3886 | mejdrech | 159 | } |
3901 | mejdrech | 160 | ( * map )[ PACKET_MAP_INDEX( packet->packet_id ) ] = packet; |
4582 | mejdrech | 161 | fibril_rwlock_write_unlock( & pm_globals.lock ); |
3886 | mejdrech | 162 | return EOK; |
163 | } |
||
164 | |||
3901 | mejdrech | 165 | void pm_destroy( void ){ |
166 | int count; |
||
167 | int index; |
||
168 | packet_map_ref map; |
||
169 | packet_t packet; |
||
3886 | mejdrech | 170 | |
4582 | mejdrech | 171 | fibril_rwlock_write_lock( & pm_globals.lock ); |
3912 | mejdrech | 172 | count = gpm_count( & pm_globals.packet_map ); |
3901 | mejdrech | 173 | while( count > 0 ){ |
3912 | mejdrech | 174 | map = gpm_get_index( & pm_globals.packet_map, count - 1 ); |
3901 | mejdrech | 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 | } |
||
3912 | mejdrech | 182 | gpm_destroy( & pm_globals.packet_map ); |
3914 | mejdrech | 183 | // leave locked |
3886 | mejdrech | 184 | } |
185 | |||
4731 | mejdrech | 186 | packet_t pq_add( packet_t first, packet_t packet, size_t order, size_t metric ){ |
3901 | mejdrech | 187 | packet_t item; |
3886 | mejdrech | 188 | |
3901 | mejdrech | 189 | if( ! packet_is_valid( packet )) return NULL; |
4731 | mejdrech | 190 | pq_set_order( packet, order, metric ); |
3901 | mejdrech | 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; |
||
4731 | mejdrech | 208 | return item ? first : packet; |
3901 | mejdrech | 209 | } |
210 | }while( packet_is_valid( item )); |
||
211 | } |
||
212 | return packet; |
||
3886 | mejdrech | 213 | } |
214 | |||
4731 | mejdrech | 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 | |||
4505 | mejdrech | 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 | |||
3901 | mejdrech | 242 | packet_t pq_detach( packet_t packet ){ |
243 | packet_t next; |
||
244 | packet_t previous; |
||
3886 | mejdrech | 245 | |
3901 | mejdrech | 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 | } |
||
3886 | mejdrech | 254 | } |
3901 | mejdrech | 255 | packet->previous = 0; |
256 | packet->next = 0; |
||
257 | return next; |
||
3886 | mejdrech | 258 | } |
259 | |||
4731 | mejdrech | 260 | int pq_set_order( packet_t packet, size_t order, size_t metric ){ |
3886 | mejdrech | 261 | if( ! packet_is_valid( packet )) return EINVAL; |
3901 | mejdrech | 262 | packet->order = order; |
263 | packet->metric = metric; |
||
264 | return EOK; |
||
3886 | mejdrech | 265 | } |
266 | |||
4731 | mejdrech | 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 | |||
3901 | mejdrech | 274 | void pq_destroy( packet_t first, void ( * packet_release )( packet_t packet )){ |
275 | packet_t actual; |
||
276 | packet_t next; |
||
3886 | mejdrech | 277 | |
3901 | mejdrech | 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 | } |
||
3886 | mejdrech | 286 | } |
287 | |||
4075 | mejdrech | 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 | |||
3886 | mejdrech | 298 | /** @} |
299 | */ |