lib/core-net/lws-dsh.c

   1 /*
   2  * libwebsockets - small server side websockets and web server implementation
   3  *
   4  * Copyright (C) 2010-2019 Andy Green <andy@warmcat.com>
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation:
   9  *  version 2.1 of the License.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19  *  MA  02110-1301  USA
  20  */
  21
  22 #include "core/private.h"
  23
  24 struct lws_dsh_search {
  25         size_t          required;
  26         int             kind;
  27         lws_dsh_obj_t   *best;
  28         lws_dsh_t       *dsh;
  29
  30         lws_dsh_t       *already_checked;
  31         lws_dsh_t       *this_dsh;
  32 };
  33
  34 static int
  35 _lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
  36                     const void *src2, size_t size2, lws_dll2_t *replace);
  37
  38 static size_t
  39 lws_dsh_align(size_t length)
  40 {
  41         size_t align = sizeof(int *);
  42
  43         if (length & (align - 1))
  44                 length += align - (length & (align - 1));
  45
  46         return length;
  47 }
  48
  49 lws_dsh_t *
  50 lws_dsh_create(lws_dll2_owner_t *owner, size_t buf_len, int count_kinds)
  51 {
  52         size_t oha_len = sizeof(lws_dsh_obj_head_t) * ++count_kinds;
  53         lws_dsh_obj_t *obj;
  54         lws_dsh_t *dsh;
  55         int n;
  56
  57         assert(buf_len);
  58         assert(count_kinds > 1);
  59
  60         dsh = lws_malloc(sizeof(lws_dsh_t) + buf_len + oha_len, __func__);
  61         if (!dsh)
  62                 return NULL;
  63
  64         /* set convenience pointers to the overallocated parts */
  65
  66         dsh->oha = (lws_dsh_obj_head_t *)&dsh[1];
  67         dsh->buf = ((uint8_t *)dsh->oha) + oha_len;
  68         dsh->count_kinds = count_kinds;
  69         dsh->buffer_size = buf_len;
  70         dsh->being_destroyed = 0;
  71
  72         /* clear down the obj heads array */
  73
  74         memset(dsh->oha, 0, oha_len);
  75         for (n = 0; n < count_kinds; n++)
  76                 dsh->oha[n].kind = n;
  77
  78         /* initially the whole buffer is on the free kind (0) list */
  79
  80         obj = (lws_dsh_obj_t *)dsh->buf;
  81         memset(obj, 0, sizeof(*obj));
  82         obj->asize = buf_len - sizeof(*obj);
  83
  84         lws_dll2_add_head(&obj->list, &dsh->oha[0].owner);
  85
  86         dsh->locally_free = obj->asize;
  87         dsh->locally_in_use = 0;
  88
  89         lws_dll2_clear(&dsh->list);
  90         if (owner)
  91                 lws_dll2_add_head(&dsh->list, owner);
  92
  93         // lws_dsh_describe(dsh, "post-init");
  94
  95         return dsh;
  96 }
  97
  98 static int
  99 search_best_free(struct lws_dll2 *d, void *user)
 100 {
 101         struct lws_dsh_search *s = (struct lws_dsh_search *)user;
 102         lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
 103
 104         lwsl_debug("%s: obj %p, asize %zu (req %zu)\n", __func__, obj,
 105                         obj->asize, s->required);
 106
 107         if (obj->asize >= s->required &&
 108             (!s->best || obj->asize < s->best->asize)) {
 109                 s->best = obj;
 110                 s->dsh = s->this_dsh;
 111         }
 112
 113         return 0;
 114 }
 115
 116 static int
 117 try_foreign(struct lws_dll2 *d, void *user)
 118 {
 119         struct lws_dsh_search *s = (struct lws_dsh_search *)user;
 120         lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
 121
 122         if (dsh1 == s->already_checked)
 123                 return 0;
 124
 125         if (dsh1->being_destroyed)
 126                 return 0;
 127
 128         if (dsh1->count_kinds < s->kind + 1)
 129                 return 0;
 130
 131         lwsl_debug("%s: actual try_foreign: dsh %p (free list size %d)\n",
 132                         __func__, dsh1, dsh1->oha[0].owner.count);
 133
 134         s->this_dsh = dsh1;
 135         if (lws_dll2_foreach_safe(&dsh1->oha[0].owner, s, search_best_free))
 136                 return 1;
 137
 138         return 0;
 139 }
 140
 141 static int
 142 free_foreign(struct lws_dll2 *d, void *user)
 143 {
 144         lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
 145         lws_dsh_t *dsh = (lws_dsh_t *)user;
 146         void *p = (void *)&obj[1];
 147
 148         if (obj->dsh != dsh)
 149                 lws_dsh_free(&p);
 150
 151         return 0;
 152 }
 153
 154 static int
 155 evict2(struct lws_dll2 *d, void *user)
 156 {
 157         lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
 158         lws_dsh_t *dsh = (lws_dsh_t *)user;
 159         void *p;
 160
 161         if (obj->dsh != dsh)
 162                 return 0;
 163
 164         /*
 165          * If we are here, it means obj is a live object that is allocated on
 166          * the dsh being destroyed, from a different dsh.  We need to migrate
 167          * the object to a dsh that isn't being destroyed.
 168          */
 169
 170         lwsl_debug("%s: migrating object size %zu\n", __func__, obj->size);
 171
 172         if (_lws_dsh_alloc_tail(dsh, 0, (void *)&obj[1], obj->size, NULL, 0, &obj->list)) {
 173                 lwsl_notice("%s: failed to migrate object\n", __func__);
 174                 /*
 175                  * only thing we can do is drop the logical object
 176                  */
 177                 p = (uint8_t *)&obj[1];
 178                 lws_dsh_free(&p);
 179         }
 180
 181         return 0;
 182 }
 183
 184 static int
 185 evict1(struct lws_dll2 *d, void *user)
 186 {
 187         lws_dsh_t *dsh1 = lws_container_of(d, lws_dsh_t, list);
 188         lws_dsh_t *dsh = (lws_dsh_t *)user;
 189         int n;
 190
 191         if (dsh1->being_destroyed)
 192                 return 0;
 193
 194         /*
 195          * For every dsh that's not being destroyed, send every object to
 196          * evict2 for checking.
 197          */
 198
 199         lwsl_debug("%s: checking dsh %p\n", __func__, dsh1);
 200
 201         for (n = 1; n < dsh1->count_kinds; n++) {
 202                 lws_dll2_describe(&dsh1->oha[n].owner, "check dsh1");
 203                 lws_dll2_foreach_safe(&dsh1->oha[n].owner, dsh, evict2);
 204         }
 205
 206         return 0;
 207 }
 208
 209 void
 210 lws_dsh_destroy(lws_dsh_t **pdsh)
 211 {
 212         lws_dsh_t *dsh = *pdsh;
 213         int n;
 214
 215         if (!dsh)
 216                 return;
 217
 218         lwsl_debug("%s: destroying dsh %p\n", __func__, dsh);
 219
 220         dsh->being_destroyed = 1;
 221
 222         /* we need to explicitly free any of our allocations in foreign dsh */
 223
 224         for (n = 1; n < dsh->count_kinds; n++)
 225                 lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, free_foreign);
 226
 227         /*
 228          * We need to have anybody else with allocations in us evict them
 229          * and make a copy in a buffer that isn't being destroyed
 230          */
 231
 232         if (dsh->list.owner)
 233                 lws_dll2_foreach_safe(dsh->list.owner, dsh, evict1);
 234
 235         lws_dll2_remove(&dsh->list);
 236
 237         /* everything else is in one heap allocation */
 238
 239         lws_free_set_NULL(*pdsh);
 240 }
 241
 242 static int
 243 _lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
 244                     const void *src2, size_t size2, lws_dll2_t *replace)
 245 {
 246         size_t asize = sizeof(lws_dsh_obj_t) + lws_dsh_align(size1 + size2);
 247         struct lws_dsh_search s;
 248
 249         assert(kind >= 0);
 250         kind++;
 251         assert(!dsh || kind < dsh->count_kinds);
 252
 253         /*
 254          * Search our free list looking for the smallest guy who will fit
 255          * what we want to allocate
 256          */
 257         s.required = asize;
 258         s.kind = kind;
 259         s.best = NULL;
 260         s.already_checked = NULL;
 261         s.this_dsh = dsh;
 262
 263         if (dsh && !dsh->being_destroyed)
 264                 lws_dll2_foreach_safe(&dsh->oha[0].owner, &s, search_best_free);
 265
 266         if (!s.best) {
 267                 /*
 268                  * Let's see if any other buffer has room
 269                  */
 270                 s.already_checked = dsh;
 271
 272                 if (dsh->list.owner)
 273                         lws_dll2_foreach_safe(dsh->list.owner, &s, try_foreign);
 274
 275                 if (!s.best) {
 276                         lwsl_notice("%s: no buffer has space\n", __func__);
 277
 278                         return 1;
 279                 }
 280         }
 281
 282         /* anything coming out of here must be aligned */
 283         assert(!(((unsigned long)s.best) & (sizeof(int *) - 1)));
 284
 285         if (s.best->asize < asize + (2 * sizeof(*s.best))) {
 286                 /*
 287                  * Exact fit, or close enough we can't / don't want to have to
 288                  * track the little bit of free area that would be left.
 289                  *
 290                  * Move the object from the free list to the oha of the
 291                  * desired kind
 292                  */
 293                 lws_dll2_remove(&s.best->list);
 294                 s.best->dsh = s.dsh;
 295                 s.best->size = size1 + size2;
 296                 memcpy(&s.best[1], src1, size1);
 297                 if (src2)
 298                         memcpy((uint8_t *)&s.best[1] + size1, src2, size2);
 299
 300                 if (replace) {
 301                         s.best->list.prev = replace->prev;
 302                         s.best->list.next = replace->next;
 303                         s.best->list.owner = replace->owner;
 304                         if (replace->prev)
 305                                 replace->prev->next = &s.best->list;
 306                         if (replace->next)
 307                                 replace->next->prev = &s.best->list;
 308                 } else
 309                         lws_dll2_add_tail(&s.best->list, &dsh->oha[kind].owner);
 310
 311                 assert(s.dsh->locally_free >= s.best->asize);
 312                 s.dsh->locally_free -= s.best->asize;
 313                 s.dsh->locally_in_use += s.best->asize;
 314                 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
 315         } else {
 316                 lws_dsh_obj_t *obj;
 317
 318                 /*
 319                  * Free area was oversize enough that we need to split it.
 320                  *
 321                  * Leave the first part of the free area where it is and
 322                  * reduce its extent by our asize.  Use the latter part of
 323                  * the original free area as the allocation.
 324                  */
 325                 lwsl_debug("%s: splitting... free reduce %zu -> %zu\n",
 326                                 __func__, s.best->asize, s.best->asize - asize);
 327
 328                 s.best->asize -= asize;
 329
 330                 /* latter part becomes new object */
 331
 332                 obj = (lws_dsh_obj_t *)(((uint8_t *)s.best) + s.best->asize);
 333
 334                 lws_dll2_clear(&obj->list);
 335                 obj->dsh = s.dsh;
 336                 obj->size = size1 + size2;
 337                 obj->asize = asize;
 338
 339                 memcpy(&obj[1], src1, size1);
 340                 if (src2)
 341                         memcpy((uint8_t *)&obj[1] + size1, src2, size2);
 342
 343                 if (replace) {
 344                         s.best->list.prev = replace->prev;
 345                         s.best->list.next = replace->next;
 346                         s.best->list.owner = replace->owner;
 347                         if (replace->prev)
 348                                 replace->prev->next = &s.best->list;
 349                         if (replace->next)
 350                                 replace->next->prev = &s.best->list;
 351                 } else
 352                         lws_dll2_add_tail(&obj->list, &dsh->oha[kind].owner);
 353
 354                 assert(s.dsh->locally_free >= asize);
 355                 s.dsh->locally_free -= asize;
 356                 s.dsh->locally_in_use += asize;
 357                 assert(s.dsh->locally_in_use <= s.dsh->buffer_size);
 358         }
 359
 360         // lws_dsh_describe(dsh, "post-alloc");
 361
 362         return 0;
 363 }
 364
 365 int
 366 lws_dsh_alloc_tail(lws_dsh_t *dsh, int kind, const void *src1, size_t size1,
 367                    const void *src2, size_t size2)
 368 {
 369         return _lws_dsh_alloc_tail(dsh, kind, src1, size1, src2, size2, NULL);
 370 }
 371
 372 static int
 373 buf_compare(const lws_dll2_t *d, const lws_dll2_t *i)
 374 {
 375         return (int)lws_ptr_diff(d, i);
 376 }
 377
 378 void
 379 lws_dsh_free(void **pobj)
 380 {
 381         lws_dsh_obj_t *_o = (lws_dsh_obj_t *)((uint8_t *)(*pobj) - sizeof(*_o)),
 382                         *_o2;
 383         lws_dsh_t *dsh = _o->dsh;
 384
 385         /* anything coming out of here must be aligned */
 386         assert(!(((unsigned long)_o) & (sizeof(int *) - 1)));
 387
 388         /*
 389          * Remove the object from its list and place on the free list of the
 390          * dsh the buffer space belongs to
 391          */
 392
 393         lws_dll2_remove(&_o->list);
 394         *pobj = NULL;
 395
 396         assert(dsh->locally_in_use >= _o->asize);
 397         dsh->locally_free += _o->asize;
 398         dsh->locally_in_use -= _o->asize;
 399         assert(dsh->locally_in_use <= dsh->buffer_size);
 400
 401         /*
 402          * The free space list is sorted in buffer address order, so detecting
 403          * coalescing opportunities is cheap.  Because the free list should be
 404          * continuously tending to reduce by coalescing, the sorting should not
 405          * be expensive to maintain.
 406          */
 407         _o->size = 0; /* not meaningful when on free list */
 408         lws_dll2_add_sorted(&_o->list, &_o->dsh->oha[0].owner, buf_compare);
 409
 410         /* First check for already-free block at the end we can subsume.
 411          * Because the free list is sorted, if there is such a guy he is
 412          * already our list.next */
 413
 414         _o2 = (lws_dsh_obj_t *)_o->list.next;
 415         if (_o2 && (uint8_t *)_o + _o->asize == (uint8_t *)_o2) {
 416                 /*
 417                  * since we are freeing _obj, we can coalesce with a
 418                  * free area immediately ahead of it
 419                  *
 420                  *  [ _o (being freed) ][ _o2 (free) ]  -> [ larger _o ]
 421                  */
 422                 _o->asize += _o2->asize;
 423
 424                 /* guy next to us was absorbed into us */
 425                 lws_dll2_remove(&_o2->list);
 426         }
 427
 428         /* Then check if we can be subsumed by a free block behind us.
 429          * Because the free list is sorted, if there is such a guy he is
 430          * already our list.prev */
 431
 432         _o2 = (lws_dsh_obj_t *)_o->list.prev;
 433         if (_o2 && (uint8_t *)_o2 + _o2->asize == (uint8_t *)_o) {
 434                 /*
 435                  * since we are freeing obj, we can coalesce it with
 436                  * the previous free area that abuts it
 437                  *
 438                  *  [ _o2 (free) ][ _o (being freed) ] -> [ larger _o2 ]
 439                  */
 440                 _o2->asize += _o->asize;
 441
 442                 /* we were absorbed! */
 443                 lws_dll2_remove(&_o->list);
 444         }
 445
 446         // lws_dsh_describe(dsh, "post-alloc");
 447 }
 448
 449 int
 450 lws_dsh_get_head(lws_dsh_t *dsh, int kind, void **obj, size_t *size)
 451 {
 452         lws_dsh_obj_t *_obj = (lws_dsh_obj_t *)
 453                         lws_dll2_get_head(&dsh->oha[kind + 1].owner);
 454
 455         if (!_obj) {
 456                 *obj = 0;
 457                 *size = 0;
 458
 459                 return 1;       /* there is no head */
 460         }
 461
 462         *obj = (void *)(&_obj[1]);
 463         *size = _obj->size;
 464
 465         /* anything coming out of here must be aligned */
 466         assert(!(((unsigned long)(*obj)) & (sizeof(int *) - 1)));
 467
 468         return 0;       /* we returned the head */
 469 }
 470
 471 #if defined(_DEBUG)
 472
 473 static int
 474 describe_kind(struct lws_dll2 *d, void *user)
 475 {
 476         lws_dsh_obj_t *obj = lws_container_of(d, lws_dsh_obj_t, list);
 477
 478         lwsl_info("    _obj %p - %p, dsh %p, size %zu, asize %zu\n",
 479                         obj, (uint8_t *)obj + obj->asize,
 480                         obj->dsh, obj->size, obj->asize);
 481
 482         return 0;
 483 }
 484
 485 void
 486 lws_dsh_describe(lws_dsh_t *dsh, const char *desc)
 487 {
 488         int n = 0;
 489
 490         lwsl_info("%s: dsh %p, bufsize %zu, kinds %d, lf: %zu, liu: %zu, %s\n",
 491                     __func__, dsh, dsh->buffer_size, dsh->count_kinds,
 492                     dsh->locally_free, dsh->locally_in_use, desc);
 493
 494         for (n = 0; n < dsh->count_kinds; n++) {
 495                 lwsl_info("  Kind %d:\n", n);
 496                 lws_dll2_foreach_safe(&dsh->oha[n].owner, dsh, describe_kind);
 497         }
 498 }
 499 #endif