Subversion Repositories HelenOS

Rev

Rev 4192 | Rev 4582 | Go to most recent revision | 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>
3990 mejdrech 41
#include <rwlock.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.
59
 *  @param packet_id The packet identifier.
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.
64
 *  @param packet_id The packet identifier.
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.
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 );
3901 mejdrech 87
 
3912 mejdrech 88
/** Packet map global data.
89
 */
3901 mejdrech 90
static struct{
3914 mejdrech 91
    /** Safety lock.
92
     */
3990 mejdrech 93
    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
 
3990 mejdrech 109
    rwlock_initialize( & pm_globals.lock );
110
    rwlock_write_lock( & pm_globals.lock );
3914 mejdrech 111
    ERROR_PROPAGATE( gpm_initialize( & pm_globals.packet_map ));
3990 mejdrech 112
    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;
3990 mejdrech 121
    rwlock_read_lock( & pm_globals.lock );
3914 mejdrech 122
    if( packet_id > PACKET_MAP_SIZE * gpm_count( & pm_globals.packet_map )){
3990 mejdrech 123
        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 ){
3990 mejdrech 128
        rwlock_read_unlock( & pm_globals.lock );
3914 mejdrech 129
        return NULL;
130
    }
131
    packet = ( * map )[ PACKET_MAP_INDEX( packet_id ) ];
3990 mejdrech 132
    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;
3990 mejdrech 142
    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 ){
3990 mejdrech 149
                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 ){
3990 mejdrech 154
                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;
3990 mejdrech 161
    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
 
3990 mejdrech 171
    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
 
3901 mejdrech 186
packet_t pq_add( packet_t first, packet_t packet, int order, size_t metric ){
187
    packet_t    item;
3886 mejdrech 188
 
3901 mejdrech 189
    if( ! packet_is_valid( packet )) return NULL;
190
    pq_set( 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;
209
            }
210
        }while( packet_is_valid( item ));
211
    }
212
    return packet;
3886 mejdrech 213
}
214
 
4505 mejdrech 215
int pq_insert_after( packet_t packet, packet_t new_packet ){
216
    packet_t    item;
217
 
218
    if( !( packet_is_valid( packet ) && packet_is_valid( new_packet ))) return EINVAL;
219
    new_packet->previous = packet->packet_id;
220
    new_packet->next = packet->next;
221
    item = pm_find( packet->next );
222
    if( item ) item->previous = new_packet->packet_id;
223
    packet->next = new_packet->packet_id;
224
    return EOK;
225
}
226
 
3901 mejdrech 227
packet_t pq_detach( packet_t packet ){
228
    packet_t next;
229
    packet_t previous;
3886 mejdrech 230
 
3901 mejdrech 231
    if( ! packet_is_valid( packet )) return NULL;
232
    next = pm_find( packet->next );
233
    if( next ){
234
        next->previous = packet->previous;
235
        previous = pm_find( next->previous );
236
        if( previous ){
237
            previous->next = next->packet_id;
238
        }
3886 mejdrech 239
    }
3901 mejdrech 240
    packet->previous = 0;
241
    packet->next = 0;
242
    return next;
3886 mejdrech 243
}
244
 
3901 mejdrech 245
int pq_set( packet_t packet, int order, size_t metric ){
3886 mejdrech 246
    if( ! packet_is_valid( packet )) return EINVAL;
3901 mejdrech 247
    packet->order = order;
248
    packet->metric = metric;
249
    return EOK;
3886 mejdrech 250
}
251
 
3901 mejdrech 252
void pq_destroy( packet_t first, void ( * packet_release )( packet_t packet )){
253
    packet_t    actual;
254
    packet_t    next;
3886 mejdrech 255
 
3901 mejdrech 256
    actual = first;
257
    while( packet_is_valid( actual )){
258
        next = pm_find( actual->next );
259
        actual->next = 0;
260
        actual->previous = 0;
261
        if( packet_release ) packet_release( actual );
262
        actual = next;
263
    }
3886 mejdrech 264
}
265
 
4075 mejdrech 266
packet_t pq_next( packet_t packet ){
267
    if( ! packet_is_valid( packet )) return NULL;
268
    return pm_find( packet->next );
269
}
270
 
271
packet_t pq_previous( packet_t packet ){
272
    if( ! packet_is_valid( packet )) return NULL;
273
    return pm_find( packet->previous );
274
}
275
 
3886 mejdrech 276
/** @}
277
 */