ircd/msgq.c

   1 /*
   2  * IRC - Internet Relay Chat, ircd/msgq.c
   3  * Copyright (C) 2000 Kevin L. Mitchell <klmitch@mit.edu>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 1, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *
  19  * $Id$
  20  */
  21 #include "config.h"
  22
  23 #include "msgq.h"
  24 #include "ircd.h"
  25 #include "ircd_alloc.h"
  26 #include "ircd_defs.h"
  27 #include "ircd_features.h"
  28 #include "ircd_reply.h"
  29 #include "ircd_snprintf.h"
  30 #include "numeric.h"
  31 #include "send.h"
  32 #include "s_debug.h"
  33 #include "s_stats.h"
  34
  35 #include <assert.h>
  36 #include <stdarg.h>
  37 #include <string.h>
  38 #include <sys/types.h>
  39 #include <sys/uio.h>    /* struct iovec */
  40
  41 #define MB_BASE_SHIFT   5
  42 #define MB_MAX_SHIFT    9
  43
  44 struct MsgBuf {
  45   struct MsgBuf *next;          /* next msg in global queue */
  46   struct MsgBuf **prev_p;       /* what points to us in linked list */
  47   struct MsgBuf *real;          /* the actual MsgBuf we're attaching */
  48   unsigned int ref;             /* reference count */
  49   unsigned int length;          /* length of message */
  50   unsigned int power;           /* size of buffer (power of 2) */
  51   char msg[1];                  /* the message */
  52 };
  53
  54 #define bufsize(buf)    (1 << (buf)->power)
  55
  56 struct Msg {
  57   struct Msg *next;             /* next msg */
  58   unsigned int sent;            /* bytes in msg that have already been sent */
  59   struct MsgBuf *msg;           /* actual message in queue */
  60 };
  61
  62 struct MsgSizes {
  63   unsigned int msgs;            /* total number of messages */
  64   unsigned int sizes[BUFSIZE];  /* histogram of message sizes */
  65 };
  66
  67 static struct {
  68   struct MsgBuf *msglist;       /* list of in-use MsgBuf's */
  69   struct {
  70     unsigned int alloc;         /* number of Msg's allocated */
  71     unsigned int used;          /* number of Msg's in use */
  72     struct Msg *free;           /* freelist of Msg's */
  73   } msgs;
  74   size_t tot_bufsize;           /* total amount of memory in buffers */
  75   struct {
  76     unsigned int alloc;         /* total MsgBuf's of this size */
  77     unsigned int used;          /* number of MsgBuf's of this size in use */
  78     struct MsgBuf *free;        /* list of free MsgBuf's */
  79   } msgBufs[MB_MAX_SHIFT - MB_BASE_SHIFT + 1];
  80   struct MsgSizes sizes;        /* histogram of message sizes */
  81 } MQData;
  82
  83 /*
  84  * This routine is used to remove a certain amount of data from a given
  85  * queue and release the Msg (and MsgBuf) structure if needed
  86  */
  87 static void
  88 msgq_delmsg(struct MsgQ *mq, struct MsgQList *qlist, unsigned int *length_p)
  89 {
  90   struct Msg *m;
  91   unsigned int msglen;
  92
  93   assert(0 != mq);
  94   assert(0 != qlist);
  95   assert(0 != qlist->head);
  96   assert(0 != length_p);
  97
  98   m = qlist->head; /* find the msg we're deleting from */
  99
 100   msglen = m->msg->length - m->sent; /* calculate how much is left */
 101
 102   if (*length_p >= msglen) { /* deleted it all? */
 103     mq->length -= msglen; /* decrement length */
 104     mq->count--; /* decrement the message count */
 105     *length_p -= msglen;
 106
 107     msgq_clean(m->msg); /* free up the struct MsgBuf */
 108     m->msg = 0; /* don't let it point anywhere nasty, please */
 109
 110     if (qlist->head == qlist->tail) /* figure out if we emptied the queue */
 111       qlist->head = qlist->tail = 0;
 112     else
 113       qlist->head = m->next; /* just shift the list down some */
 114
 115     MQData.msgs.used--; /* struct Msg is not in use anymore */
 116
 117     m->next = MQData.msgs.free; /* throw it onto the free list */
 118     MQData.msgs.free = m;
 119   } else {
 120     mq->length -= *length_p; /* decrement queue length */
 121     m->sent += *length_p; /* this much of the message has been sent */
 122     *length_p = 0; /* we've dealt with it all */
 123   }
 124 }
 125
 126 /*
 127  * This just initializes a struct MsgQ.
 128  */
 129 void
 130 msgq_init(struct MsgQ *mq)
 131 {
 132   assert(0 != mq);
 133
 134   mq->length = 0;
 135   mq->count = 0;
 136   mq->queue.head = 0;
 137   mq->queue.tail = 0;
 138   mq->prio.head = 0;
 139   mq->prio.tail = 0;
 140 }
 141
 142 /*
 143  * This routine is used to delete the specified number of bytes off
 144  * of the queue.  We only really need to worry about one struct Msg*,
 145  * but this allows us to retain the flexibility to deal with more,
 146  * which means we could do something fancy involving writev...
 147  */
 148 void
 149 msgq_delete(struct MsgQ *mq, unsigned int length)
 150 {
 151   assert(0 != mq);
 152
 153   while (length > 0) {
 154     if (mq->queue.head && mq->queue.head->sent > 0) /* partial msg on norm q */
 155       msgq_delmsg(mq, &mq->queue, &length);
 156     else if (mq->prio.head) /* message (partial or complete) on prio queue */
 157       msgq_delmsg(mq, &mq->prio, &length);
 158     else if (mq->queue.head) /* message on normal queue */
 159       msgq_delmsg(mq, &mq->queue, &length);
 160     else
 161       break;
 162   }
 163 }
 164
 165 /*
 166  * This is the more intelligent routine that can fill in an array of
 167  * struct iovec's.
 168  */
 169 int
 170 msgq_mapiov(const struct MsgQ *mq, struct iovec *iov, int count,
 171             unsigned int *len)
 172 {
 173   struct Msg *queue;
 174   struct Msg *prio;
 175   int i = 0;
 176
 177   assert(0 != mq);
 178   assert(0 != iov);
 179   assert(0 != count);
 180   assert(0 != len);
 181
 182   if (mq->length <= 0) /* no data to map */
 183     return 0;
 184
 185   if (mq->queue.head && mq->queue.head->sent > 0) { /* partial msg on norm q */
 186     iov[i].iov_base = mq->queue.head->msg->msg + mq->queue.head->sent;
 187     iov[i].iov_len = mq->queue.head->msg->length - mq->queue.head->sent;
 188     *len += iov[i].iov_len;
 189
 190     queue = mq->queue.head->next; /* where we start later... */
 191
 192     i++; /* filled an iovec... */
 193     if (!--count) /* check for space */
 194       return i;
 195   } else
 196     queue = mq->queue.head; /* start at head of queue */
 197
 198   if (mq->prio.head && mq->prio.head->sent > 0) { /* partial msg on prio q */
 199     iov[i].iov_base = mq->prio.head->msg->msg + mq->prio.head->sent;
 200     iov[i].iov_len = mq->prio.head->msg->length - mq->prio.head->sent;
 201     *len += iov[i].iov_len;
 202
 203     prio = mq->prio.head->next; /* where we start later... */
 204
 205     i++; /* filled an iovec... */
 206     if (!--count) /* check for space */
 207       return i;
 208   } else
 209     prio = mq->prio.head; /* start at head of prio */
 210
 211   for (; prio; prio = prio->next) { /* go through prio queue */
 212     iov[i].iov_base = prio->msg->msg; /* store message */
 213     iov[i].iov_len = prio->msg->length;
 214     *len += iov[i].iov_len;
 215
 216     i++; /* filled an iovec... */
 217     if (!--count) /* check for space */
 218       return i;
 219   }
 220
 221   for (; queue; queue = queue->next) { /* go through normal queue */
 222     iov[i].iov_base = queue->msg->msg;
 223     iov[i].iov_len = queue->msg->length;
 224     *len += iov[i].iov_len;
 225
 226     i++; /* filled an iovec... */
 227     if (!--count) /* check for space */
 228       return i;
 229   }
 230
 231   return i;
 232 }
 233
 234 /*
 235  * This is a helper routine to allocate a buffer
 236  */
 237 static struct MsgBuf *
 238 msgq_alloc(struct MsgBuf *in_mb, int length)
 239 {
 240   struct MsgBuf *mb;
 241   int power;
 242
 243   /* Find the power of two size that will accomodate the message */
 244   for (power = MB_BASE_SHIFT; power < MB_MAX_SHIFT + 1; power++)
 245     if ((length - 1) >> power == 0)
 246       break;
 247   assert((1 << power) >= length);
 248   assert((1 << power) <= 512);
 249   length = 1 << power; /* reset the length */
 250
 251   /* If the message needs a buffer of exactly the existing size, just use it */
 252   if (in_mb && in_mb->power == power) {
 253     in_mb->real = in_mb; /* real buffer is this buffer */
 254     return in_mb;
 255   }
 256
 257   /* Try popping one off the freelist first */
 258   if ((mb = MQData.msgBufs[power - MB_BASE_SHIFT].free)) {
 259     MQData.msgBufs[power - MB_BASE_SHIFT].free = mb->next;
 260   } else if (MQData.tot_bufsize < feature_int(FEAT_BUFFERPOOL)) {
 261     /* Allocate another if we won't bust the BUFFERPOOL */
 262     Debug((DEBUG_MALLOC, "Allocating MsgBuf of length %d (total size %zu)",
 263            length, sizeof(struct MsgBuf) + length));
 264     mb = (struct MsgBuf *)MyMalloc(sizeof(struct MsgBuf) + length);
 265     MQData.msgBufs[power - MB_BASE_SHIFT].alloc++;
 266     mb->power = power; /* remember size */
 267     MQData.tot_bufsize += length;
 268   }
 269
 270   if (mb) {
 271     MQData.msgBufs[power - MB_BASE_SHIFT].used++; /* how many are we using? */
 272
 273     mb->real = 0; /* essential initializations */
 274     mb->ref = 1;
 275
 276     if (in_mb) /* remember who's the *real* buffer */
 277       in_mb->real = mb;
 278   } else if (in_mb) /* just use the input buffer */
 279     mb = in_mb->real = in_mb;
 280
 281   return mb; /* return the buffer */
 282 }
 283
 284 /*
 285  * This routine simply empties the free list
 286  */
 287 static void
 288 msgq_clear_freembs(void)
 289 {
 290   struct MsgBuf *mb;
 291   int i;
 292
 293   /* Walk through the various size classes */
 294   for (i = MB_BASE_SHIFT; i < MB_MAX_SHIFT + 1; i++)
 295     /* walk down the free list */
 296     while ((mb = MQData.msgBufs[i - MB_BASE_SHIFT].free)) {
 297       MQData.msgBufs[i - MB_BASE_SHIFT].free = mb->next; /* shift free list */
 298       MQData.msgBufs[i - MB_BASE_SHIFT].alloc--; /* reduce allocation count */
 299       MQData.tot_bufsize -= 1 << i; /* reduce total buffer allocation count */
 300       MyFree(mb); /* and free the buffer */
 301     }
 302 }
 303
 304 /*
 305  * This routine builds a struct MsgBuf with the appropriate contents
 306  * and returns it; this saves us from having to worry about the contents
 307  * of struct MsgBuf in anything other than this module
 308  */
 309 struct MsgBuf *
 310 msgq_vmake(struct Client *dest, const char *format, va_list vl)
 311 {
 312   struct MsgBuf *mb;
 313
 314   assert(0 != format);
 315
 316   if (!(mb = msgq_alloc(0, BUFSIZE))) {
 317     if (feature_bool(FEAT_HAS_FERGUSON_FLUSHER)) {
 318       /*
 319        * from "Married With Children" episode were Al bought a REAL toilet
 320        * on the black market because he was tired of the wimpy water
 321        * conserving toilets they make these days --Bleep
 322        */
 323       /*
 324        * Apparently this doesn't work, the server _has_ to
 325        * dump a few clients to handle the load. A fully loaded
 326        * server cannot handle a net break without dumping some
 327        * clients. If we flush the connections here under a full
 328        * load we may end up starving the kernel for mbufs and
 329        * crash the machine
 330        */
 331       /*
 332        * attempt to recover from buffer starvation before
 333        * bailing this may help servers running out of memory
 334        */
 335       flush_connections(0);
 336       mb = msgq_alloc(0, BUFSIZE);
 337     }
 338     if (!mb) { /* OK, try clearing the buffer free list */
 339       msgq_clear_freembs();
 340       mb = msgq_alloc(0, BUFSIZE);
 341     }
 342     if (!mb) { /* OK, try killing a client */
 343       kill_highest_sendq(0); /* Don't kill any server connections */
 344       mb = msgq_alloc(0, BUFSIZE);
 345     }
 346     if (!mb) { /* hmmm... */
 347       kill_highest_sendq(1); /* Try killing a server connection now */
 348       mb = msgq_alloc(0, BUFSIZE);
 349     }
 350     if (!mb) /* AIEEEE! */
 351       server_panic("Unable to allocate buffers!");
 352   }
 353
 354   mb->next = MQData.msglist; /* initialize the msgbuf */
 355   mb->prev_p = &MQData.msglist;
 356
 357   /* fill the buffer */
 358   mb->length = ircd_vsnprintf(dest, mb->msg, bufsize(mb) - 1, format, vl);
 359
 360   if (mb->length > bufsize(mb) - 2)
 361     mb->length = bufsize(mb) - 2;
 362
 363   mb->msg[mb->length++] = '\r'; /* add \r\n to buffer */
 364   mb->msg[mb->length++] = '\n';
 365   mb->msg[mb->length] = '\0'; /* not strictly necessary */
 366
 367   assert(mb->length <= bufsize(mb));
 368
 369   if (MQData.msglist) /* link it into the list */
 370     MQData.msglist->prev_p = &mb->next;
 371   MQData.msglist = mb;
 372
 373   return mb;
 374 }
 375
 376 struct MsgBuf *
 377 msgq_make(struct Client *dest, const char *format, ...)
 378 {
 379   va_list vl;
 380   struct MsgBuf *mb;
 381
 382   va_start(vl, format);
 383   mb = msgq_vmake(dest, format, vl);
 384   va_end(vl);
 385
 386   return mb;
 387 }
 388
 389 /*
 390  * This routine is used to append a formatted string to a struct MsgBuf.
 391  */
 392 void
 393 msgq_append(struct Client *dest, struct MsgBuf *mb, const char *format, ...)
 394 {
 395   va_list vl;
 396
 397   assert(0 != mb);
 398   assert(0 != format);
 399   assert(0 == mb->real);
 400
 401   assert(2 < mb->length);
 402   assert(bufsize(mb) >= mb->length);
 403
 404   mb->length -= 2; /* back up to before \r\n */
 405
 406   va_start(vl, format); /* append to the buffer */
 407   mb->length += ircd_vsnprintf(dest, mb->msg + mb->length,
 408                                bufsize(mb) - mb->length - 1, format, vl);
 409   va_end(vl);
 410
 411   if (mb->length > bufsize(mb) - 2)
 412     mb->length = bufsize(mb) - 2;
 413
 414   mb->msg[mb->length++] = '\r'; /* add \r\n to buffer */
 415   mb->msg[mb->length++] = '\n';
 416   mb->msg[mb->length] = '\0'; /* not strictly necessary */
 417
 418   assert(mb->length <= bufsize(mb));
 419 }
 420
 421 /*
 422  * This routine is called to decrement the reference count on a
 423  * struct MsgBuf and delete it if necessary.
 424  */
 425 void
 426 msgq_clean(struct MsgBuf *mb)
 427 {
 428   assert(0 != mb);
 429   assert(0 < mb->ref);
 430
 431   if (!--mb->ref) { /* deallocate the message */
 432     if (mb->prev_p) {
 433       *mb->prev_p = mb->next; /* clip it out of active MsgBuf's list */
 434       if (mb->next)
 435         mb->next->prev_p = mb->prev_p;
 436     }
 437
 438     if (mb->real && mb->real != mb) /* clean up the real buffer */
 439       msgq_clean(mb->real);
 440
 441     mb->next = MQData.msgBufs[mb->power - MB_BASE_SHIFT].free;
 442     MQData.msgBufs[mb->power - MB_BASE_SHIFT].free = mb;
 443     MQData.msgBufs[mb->power - MB_BASE_SHIFT].used--;
 444
 445     mb->prev_p = 0;
 446   }
 447 }
 448
 449 /*
 450  * This routine simply adds a struct Msg to the end of a user's MsgQ.
 451  */
 452 void
 453 msgq_add(struct MsgQ *mq, struct MsgBuf *mb, int prio)
 454 {
 455   struct MsgQList *qlist;
 456   struct Msg *msg;
 457
 458   assert(0 != mq);
 459   assert(0 != mb);
 460   assert(0 < mb->ref);
 461   assert(0 < mb->length);
 462
 463   Debug((DEBUG_SEND, "Adding buffer %p [%.*s] length %u to %s queue", mb,
 464          mb->length - 2, mb->msg, mb->length, prio ? "priority" : "normal"));
 465
 466   qlist = prio ? &mq->prio : &mq->queue;
 467
 468   if (!(msg = MQData.msgs.free)) { /* do I need to allocate one? */
 469     msg = (struct Msg *)MyMalloc(sizeof(struct Msg));
 470     MQData.msgs.alloc++; /* we allocated another */
 471   } else /* shift the free list */
 472     MQData.msgs.free = MQData.msgs.free->next;
 473
 474   MQData.msgs.used++; /* we're using another */
 475
 476   msg->next = 0; /* initialize the msg */
 477   msg->sent = 0;
 478
 479   /* Get the real buffer, allocating one if necessary */
 480   if (!mb->real) {
 481     struct MsgBuf *tmp;
 482
 483     MQData.sizes.msgs++; /* update histogram counts */
 484     MQData.sizes.sizes[mb->length - 1]++;
 485
 486     tmp = msgq_alloc(mb, mb->length); /* allocate a close-fitting buffer */
 487
 488     if (tmp != mb) { /* OK, prepare the new "real" buffer */
 489       Debug((DEBUG_SEND, "Copying old buffer %p [%.*s] length %u into new "
 490              "buffer %p size %u", mb, mb->length - 2, mb->msg, mb->length,
 491              tmp, bufsize(tmp)));
 492       memcpy(tmp->msg, mb->msg, mb->length + 1); /* copy string over */
 493       tmp->length = mb->length;
 494
 495       tmp->next = mb->next; /* replace it in the list, now */
 496       if (tmp->next)
 497         tmp->next->prev_p = &tmp->next;
 498       tmp->prev_p = mb->prev_p;
 499       *tmp->prev_p = tmp;
 500
 501       mb->next = 0; /* this one's no longer in the list */
 502       mb->prev_p = 0;
 503     }
 504   }
 505
 506   mb = mb->real; /* work with the real buffer */
 507   mb->ref++; /* increment the ref count on the buffer */
 508
 509   msg->msg = mb; /* point at the real message buffer now */
 510
 511   if (!qlist->head) /* queue list was empty; head and tail point to msg */
 512     qlist->head = qlist->tail = msg;
 513   else {
 514     assert(0 != qlist->tail);
 515
 516     qlist->tail->next = msg; /* queue had something in it; add to end */
 517     qlist->tail = msg;
 518   }
 519
 520   mq->length += mb->length; /* update the queue length */
 521   mq->count++; /* and the queue count */
 522 }
 523
 524 /*
 525  * This is for reporting memory usage by the msgq system.
 526  */
 527 void
 528 msgq_count_memory(struct Client *cptr, size_t *msg_alloc, size_t *msgbuf_alloc)
 529 {
 530   int i;
 531   size_t total = 0, size;
 532
 533   assert(0 != cptr);
 534   assert(0 != msg_alloc);
 535   assert(0 != msgbuf_alloc);
 536
 537   /* Data for Msg's is simple, so just send it */
 538   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG,
 539              ":Msgs allocated %d(%zu) used %d(%zu)", MQData.msgs.alloc,
 540              MQData.msgs.alloc * sizeof(struct Msg), MQData.msgs.used,
 541              MQData.msgs.used * sizeof(struct Msg));
 542   /* count_memory() wants to know the total */
 543   *msg_alloc = MQData.msgs.alloc * sizeof(struct Msg);
 544
 545   /* Ok, now walk through each size class */
 546   for (i = MB_BASE_SHIFT; i < MB_MAX_SHIFT + 1; i++) {
 547     size = sizeof(struct MsgBuf) + (1 << i); /* total size of a buffer */
 548
 549     /* Send information for this buffer size class */
 550     send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG,
 551                ":MsgBufs of size %zu allocated %d(%zu) used %d(%zu)", 1 << i,
 552                MQData.msgBufs[i - MB_BASE_SHIFT].alloc,
 553                MQData.msgBufs[i - MB_BASE_SHIFT].alloc * size,
 554                MQData.msgBufs[i - MB_BASE_SHIFT].used,
 555                MQData.msgBufs[i - MB_BASE_SHIFT].used * size);
 556
 557     /* count_memory() wants to know the total */
 558     total += MQData.msgBufs[i - MB_BASE_SHIFT].alloc * size;
 559   }
 560   *msgbuf_alloc = total;
 561 }
 562
 563 /*
 564  * This routine is used simply to report how much bufferspace is left.
 565  */
 566 unsigned int
 567 msgq_bufleft(struct MsgBuf *mb)
 568 {
 569   assert(0 != mb);
 570
 571   return bufsize(mb) - mb->length; /* \r\n counted in mb->length */
 572 }
 573
 574 /*
 575  * This just generates and sends a histogram of message lengths to the
 576  * requesting client
 577  */
 578 void
 579 msgq_histogram(struct Client *cptr, const struct StatDesc *sd, char *param)
 580 {
 581   struct MsgSizes tmp = MQData.sizes; /* All hail structure copy! */
 582   int i;
 583
 584   send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG,
 585              ":Histogram of message lengths (%lu messages)", tmp.msgs);
 586   for (i = 0; i + 16 <= BUFSIZE; i += 16)
 587     send_reply(cptr, SND_EXPLICIT | RPL_STATSDEBUG, ":% 4d: %lu %lu %lu %lu "
 588                "%lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu", i + 1,
 589                tmp.sizes[i +  0], tmp.sizes[i +  1], tmp.sizes[i +  2],
 590                tmp.sizes[i +  3], tmp.sizes[i +  4], tmp.sizes[i +  5],
 591                tmp.sizes[i +  6], tmp.sizes[i +  7], tmp.sizes[i +  8],
 592                tmp.sizes[i +  9], tmp.sizes[i + 10], tmp.sizes[i + 11],
 593                tmp.sizes[i + 12], tmp.sizes[i + 13], tmp.sizes[i + 14],
 594                tmp.sizes[i + 15]);
 595 }