Subversion Repositories HelenOS

Rev

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
 */