gtp/queue.c

   1 /*
   2  *  OpenGGSN - Gateway GPRS Support Node
   3  *  Copyright (C) 2002, 2003, 2004 Mondru AB.
   4  *  Copyright (C) 2011 Harald Welte <laforge@gnumonks.org>
   5  *
   6  *  The contents of this file may be used under the terms of the GNU
   7  *  General Public License Version 2, provided that the above copyright
   8  *  notice and this permission notice is included in all copies or
   9  *  substantial portions of the software.
  10  *
  11  */
  12
  13 /*
  14  * Queue.c
  15  * Reliable delivery of signalling messages
  16  */
  17
  18 #include <../config.h>
  19 #ifdef HAVE_STDINT_H
  20 #include <stdint.h>
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <sys/types.h>
  26 #include <sys/time.h>
  27 #include <netinet/in.h>
  28 #include <string.h>
  29 #include "pdp.h"
  30 #include "gtp.h"
  31 #include "queue.h"
  32
  33 /*! \brief dump a queue_t to stdout */
  34 static int queue_print(struct queue_t *queue)
  35 {
  36         int n;
  37         printf("Queue: %p Next: %d First: %d Last: %d\n", queue,
  38                queue->next, queue->first, queue->last);
  39         printf("# State seq next prev timeout retrans\n");
  40         for (n = 0; n < QUEUE_SIZE; n++) {
  41                 printf("%d %d %d %d %d %d %d\n",
  42                        n,
  43                        queue->qmsga[n].state,
  44                        queue->qmsga[n].seq,
  45                        queue->qmsga[n].next,
  46                        queue->qmsga[n].prev,
  47                        (int)queue->qmsga[n].timeout, queue->qmsga[n].retrans);
  48         }
  49         return 0;
  50 }
  51
  52 /*! \brief compute the hash function */
  53 static int queue_seqhash(struct sockaddr_in *peer, uint16_t seq)
  54 {
  55         /* With QUEUE_HASH_SIZE = 2^16 this describes all possible
  56            seq values. Thus we have perfect hash for the request queue.
  57            For the response queue we might have collisions, but not very
  58            often.
  59            For performance optimisation we should remove the modulus
  60            operator, but this is only valid for QUEUE_HASH_SIZE = 2^16 */
  61         return seq % QUEUE_HASH_SIZE;
  62 }
  63
  64 /*! \brief Insert a message with given sequence number into the hash
  65  *
  66  * This function sets the peer and the seq of the qmsg and then inserts
  67  * the qmsg into the queue hash.  To do so, it does a hashtable lookup
  68  * and appends the new entry as the last into the double-linked list of
  69  * entries for this sequence number.
  70  */
  71 static int queue_seqset(struct queue_t *queue, struct qmsg_t *qmsg,
  72                         struct sockaddr_in *peer, uint16_t seq)
  73 {
  74         int hash = queue_seqhash(peer, seq);
  75         struct qmsg_t *qmsg2;
  76         struct qmsg_t *qmsg_prev = NULL;
  77
  78         if (QUEUE_DEBUG)
  79                 printf("Begin queue_seqset seq = %d\n", (int)seq);
  80         if (QUEUE_DEBUG)
  81                 printf("SIZEOF PEER %d, *PEER %d\n", sizeof(peer),
  82                        sizeof(*peer));
  83
  84         qmsg->seq = seq;
  85         memcpy(&qmsg->peer, peer, sizeof(*peer));
  86
  87         for (qmsg2 = queue->hashseq[hash]; qmsg2; qmsg2 = qmsg2->seqnext)
  88                 qmsg_prev = qmsg2;
  89         if (!qmsg_prev)
  90                 queue->hashseq[hash] = qmsg;
  91         else
  92                 qmsg_prev->seqnext = qmsg;
  93         if (QUEUE_DEBUG)
  94                 printf("End queue_seqset\n");
  95         return 0;
  96 }
  97
  98 /*! \brief Remove a given qmsg_t from the queue hash */
  99 static int queue_seqdel(struct queue_t *queue, struct qmsg_t *qmsg)
 100 {
 101         int hash = queue_seqhash(&qmsg->peer, qmsg->seq);
 102         struct qmsg_t *qmsg2;
 103         struct qmsg_t *qmsg_prev = NULL;
 104         if (QUEUE_DEBUG)
 105                 printf("Begin queue_seqdel seq = %d\n", (int)qmsg->seq);
 106
 107         for (qmsg2 = queue->hashseq[hash]; qmsg2; qmsg2 = qmsg2->seqnext) {
 108                 if (qmsg == qmsg2) {
 109                         if (!qmsg_prev)
 110                                 queue->hashseq[hash] = qmsg2->seqnext;
 111                         else
 112                                 qmsg_prev->seqnext = qmsg2->seqnext;
 113                         if (QUEUE_DEBUG)
 114                                 printf("End queue_seqdel: SEQ found\n");
 115                         return 0;
 116                 }
 117                 qmsg_prev = qmsg2;
 118         }
 119         printf("End queue_seqdel: SEQ not found\n");
 120         return EOF;             /* End of linked list and not found */
 121 }
 122
 123 /*! \brief Allocates and initialises new queue structure */
 124 int queue_new(struct queue_t **queue)
 125 {
 126         if (QUEUE_DEBUG)
 127                 printf("queue_new\n");
 128         *queue = calloc(1, sizeof(struct queue_t));
 129         if (!(*queue))
 130                 return EOF;
 131         (*queue)->next = 0;
 132         (*queue)->first = -1;
 133         (*queue)->last = -1;
 134
 135         if (QUEUE_DEBUG)
 136                 queue_print(*queue);
 137         return 0;
 138 }
 139
 140 /*! \brief Deallocates queue structure */
 141 int queue_free(struct queue_t *queue)
 142 {
 143         if (QUEUE_DEBUG)
 144                 printf("queue_free\n");
 145         if (QUEUE_DEBUG)
 146                 queue_print(queue);
 147         free(queue);
 148         return 0;
 149 }
 150
 151 /*! \brief Add a new message to the queue */
 152 int queue_newmsg(struct queue_t *queue, struct qmsg_t **qmsg,
 153                  struct sockaddr_in *peer, uint16_t seq)
 154 {
 155         if (QUEUE_DEBUG)
 156                 printf("queue_newmsg %d\n", (int)seq);
 157         if (queue->qmsga[queue->next].state == 1) {
 158                 return EOF;     /* Queue is full */
 159         } else {
 160                 *qmsg = &queue->qmsga[queue->next];
 161                 queue_seqset(queue, *qmsg, peer, seq);
 162                 (*qmsg)->state = 1;     /* Space taken */
 163                 (*qmsg)->this = queue->next;
 164                 (*qmsg)->next = -1;     /* End of the queue */
 165                 (*qmsg)->prev = queue->last;    /* Link to the previous */
 166                 if (queue->last != -1)
 167                         queue->qmsga[queue->last].next = queue->next;   /* Link previous to us */
 168                 queue->last = queue->next;      /* End of queue */
 169                 if (queue->first == -1)
 170                         queue->first = queue->next;
 171                 queue->next = (queue->next + 1) % QUEUE_SIZE;   /* Increment */
 172                 if (QUEUE_DEBUG)
 173                         queue_print(queue);
 174                 return 0;
 175         }
 176 }
 177
 178 /*! \brief Simply remoev a given qmsg_t from the queue
 179  *
 180  * Internally, we first delete the entry from the queue, and then update
 181  * up our global queue->first / queue->last pointers.  Finally,
 182  * the qmsg_t is re-initialized with zero bytes.  No memory is released.
 183  */
 184 int queue_freemsg(struct queue_t *queue, struct qmsg_t *qmsg)
 185 {
 186         if (QUEUE_DEBUG)
 187                 printf("queue_freemsg\n");
 188         if (qmsg->state != 1) {
 189                 return EOF;     /* Not in queue */
 190         }
 191
 192         queue_seqdel(queue, qmsg);
 193
 194         if (qmsg->next == -1)   /* Are we the last in queue? */
 195                 queue->last = qmsg->prev;
 196         else
 197                 queue->qmsga[qmsg->next].prev = qmsg->prev;
 198
 199         if (qmsg->prev == -1)   /* Are we the first in queue? */
 200                 queue->first = qmsg->next;
 201         else
 202                 queue->qmsga[qmsg->prev].next = qmsg->next;
 203
 204         memset(qmsg, 0, sizeof(struct qmsg_t)); /* Just to be safe */
 205
 206         if (QUEUE_DEBUG)
 207                 queue_print(queue);
 208
 209         return 0;
 210 }
 211
 212 /*! \brief Move a given qmsg_t to the end of the queue ?!? */
 213 int queue_back(struct queue_t *queue, struct qmsg_t *qmsg)
 214 {
 215         if (QUEUE_DEBUG)
 216                 printf("queue_back\n");
 217         if (qmsg->state != 1) {
 218                 return EOF;     /* Not in queue */
 219         }
 220
 221         /* Insert stuff to maintain hash table */
 222
 223         if (qmsg->next != -1) { /* Only swop if there are others */
 224                 queue->qmsga[qmsg->next].prev = qmsg->prev;
 225                 queue->first = qmsg->next;
 226
 227                 qmsg->next = -1;
 228                 qmsg->prev = queue->last;
 229                 if (queue->last != -1)
 230                         queue->qmsga[queue->last].next = qmsg->this;
 231                 queue->last = qmsg->this;
 232         }
 233         if (QUEUE_DEBUG)
 234                 queue_print(queue);
 235         return 0;
 236 }
 237
 238 /*! \brief Get the first element in the entire queue */
 239 int queue_getfirst(struct queue_t *queue, struct qmsg_t **qmsg)
 240 {
 241         /*printf("queue_getfirst\n"); */
 242         if (queue->first == -1) {
 243                 *qmsg = NULL;
 244                 return EOF;     /* End of queue = queue is empty. */
 245         }
 246         *qmsg = &queue->qmsga[queue->first];
 247         if (QUEUE_DEBUG)
 248                 queue_print(queue);
 249         return 0;
 250 }
 251
 252 /*! \brief Get a queue entry for a given peer + seq */
 253 int queue_seqget(struct queue_t *queue, struct qmsg_t **qmsg,
 254                  struct sockaddr_in *peer, uint16_t seq)
 255 {
 256         int hash = queue_seqhash(peer, seq);
 257         struct qmsg_t *qmsg2;
 258         if (QUEUE_DEBUG)
 259                 printf("Begin queue_seqget seq = %d\n", (int)seq);
 260         for (qmsg2 = queue->hashseq[hash]; qmsg2; qmsg2 = qmsg2->seqnext) {
 261                 if ((qmsg2->seq == seq) &&
 262                     (!memcmp(&qmsg2->peer, peer, sizeof(*peer)))) {
 263                         *qmsg = qmsg2;
 264                         if (QUEUE_DEBUG)
 265                                 printf("End queue_seqget. Found\n");
 266                         return 0;
 267                 }
 268         }
 269         if (QUEUE_DEBUG)
 270                 printf("End queue_seqget. Not found\n");
 271         return EOF;             /* End of linked list and not found */
 272 }
 273
 274 /*! \brief look-up a given seq/peer, return cbp + type and free entry */
 275 int queue_freemsg_seq(struct queue_t *queue, struct sockaddr_in *peer,
 276                       uint16_t seq, uint8_t * type, void **cbp)
 277 {
 278         struct qmsg_t *qmsg;
 279         if (queue_seqget(queue, &qmsg, peer, seq)) {
 280                 *cbp = NULL;
 281                 *type = 0;
 282                 return EOF;
 283         }
 284         *cbp = qmsg->cbp;
 285         *type = qmsg->type;
 286         if (queue_freemsg(queue, qmsg)) {
 287                 return EOF;
 288         }
 289         return 0;
 290 }