net/ipv4/ipvs/ip_vs_lblc.c

   1 /*
   2  * IPVS:        Locality-Based Least-Connection scheduling module
   3  *
   4  * Version:     $Id: ip_vs_lblc.c,v 1.10 2002/09/15 08:14:08 wensong Exp $
   5  *
   6  * Authors:     Wensong Zhang <wensong@gnuchina.org>
   7  *
   8  *              This program is free software; you can redistribute it and/or
   9  *              modify it under the terms of the GNU General Public License
  10  *              as published by the Free Software Foundation; either version
  11  *              2 of the License, or (at your option) any later version.
  12  *
  13  * Changes:
  14  *     Martin Hamilton         :    fixed the terrible locking bugs
  15  *                                   *lock(tbl->lock) ==> *lock(&tbl->lock)
  16  *     Wensong Zhang           :    fixed the uninitilized tbl->lock bug
  17  *     Wensong Zhang           :    added doing full expiration check to
  18  *                                   collect stale entries of 24+ hours when
  19  *                                   no partial expire check in a half hour
  20  *     Julian Anastasov        :    replaced del_timer call with del_timer_sync
  21  *                                   to avoid the possible race between timer
  22  *                                   handler and del_timer thread in SMP
  23  *
  24  */
  25
  26 /*
  27  * The lblc algorithm is as follows (pseudo code):
  28  *
  29  *       if cachenode[dest_ip] is null then
  30  *               n, cachenode[dest_ip] <- {weighted least-conn node};
  31  *       else
  32  *               n <- cachenode[dest_ip];
  33  *               if (n is dead) OR
  34  *                  (n.conns>n.weight AND
  35  *                   there is a node m with m.conns<m.weight/2) then
  36  *                 n, cachenode[dest_ip] <- {weighted least-conn node};
  37  *
  38  *       return n;
  39  *
  40  * Thanks must go to Wenzhuo Zhang for talking WCCP to me and pushing
  41  * me to write this module.
  42  */
  43
  44 #include <linux/module.h>
  45 #include <linux/kernel.h>
  46
  47 /* for sysctl */
  48 #include <linux/fs.h>
  49 #include <linux/sysctl.h>
  50
  51 #include <net/ip_vs.h>
  52
  53
  54 /*
  55  *    It is for garbage collection of stale IPVS lblc entries,
  56  *    when the table is full.
  57  */
  58 #define CHECK_EXPIRE_INTERVAL   (60*HZ)
  59 #define ENTRY_TIMEOUT           (6*60*HZ)
  60
  61 /*
  62  *    It is for full expiration check.
  63  *    When there is no partial expiration check (garbage collection)
  64  *    in a half hour, do a full expiration check to collect stale
  65  *    entries that haven't been touched for a day.
  66  */
  67 #define COUNT_FOR_FULL_EXPIRATION   30
  68 static int sysctl_ip_vs_lblc_expiration = 24*60*60*HZ;
  69
  70
  71 /*
  72  *     for IPVS lblc entry hash table
  73  */
  74 #ifndef CONFIG_IP_VS_LBLC_TAB_BITS
  75 #define CONFIG_IP_VS_LBLC_TAB_BITS      10
  76 #endif
  77 #define IP_VS_LBLC_TAB_BITS     CONFIG_IP_VS_LBLC_TAB_BITS
  78 #define IP_VS_LBLC_TAB_SIZE     (1 << IP_VS_LBLC_TAB_BITS)
  79 #define IP_VS_LBLC_TAB_MASK     (IP_VS_LBLC_TAB_SIZE - 1)
  80
  81
  82 /*
  83  *      IPVS lblc entry represents an association between destination
  84  *      IP address and its destination server
  85  */
  86 struct ip_vs_lblc_entry {
  87         struct list_head        list;
  88         __u32                   addr;           /* destination IP address */
  89         struct ip_vs_dest       *dest;          /* real server (cache) */
  90         unsigned long           lastuse;        /* last used time */
  91 };
  92
  93
  94 /*
  95  *      IPVS lblc hash table
  96  */
  97 struct ip_vs_lblc_table {
  98         rwlock_t                lock;           /* lock for this table */
  99         struct list_head        bucket[IP_VS_LBLC_TAB_SIZE];  /* hash bucket */
 100         atomic_t                entries;        /* number of entries */
 101         int                     max_size;       /* maximum size of entries */
 102         struct timer_list       periodic_timer; /* collect stale entries */
 103         int                     rover;          /* rover for expire check */
 104         int                     counter;        /* counter for no expire */
 105 };
 106
 107
 108 /*
 109  *      IPVS LBLC sysctl table
 110  */
 111
 112 static ctl_table vs_vars_table[] = {
 113         {
 114                 .ctl_name       = NET_IPV4_VS_LBLC_EXPIRE,
 115                 .procname       = "lblc_expiration",
 116                 .data           = &sysctl_ip_vs_lblc_expiration,
 117                 .maxlen         = sizeof(int),
 118                 .mode           = 0644,
 119                 .proc_handler   = &proc_dointvec_jiffies,
 120         },
 121         { .ctl_name = 0 }
 122 };
 123
 124 static ctl_table vs_table[] = {
 125         {
 126                 .ctl_name       = NET_IPV4_VS,
 127                 .procname       = "vs",
 128                 .mode           = 0555,
 129                 .child          = vs_vars_table
 130         },
 131         { .ctl_name = 0 }
 132 };
 133
 134 static ctl_table ipv4_table[] = {
 135         {
 136                 .ctl_name       = NET_IPV4,
 137                 .procname       = "ipv4",
 138                 .mode           = 0555,
 139                 .child          = vs_table
 140         },
 141         { .ctl_name = 0 }
 142 };
 143
 144 static ctl_table lblc_root_table[] = {
 145         {
 146                 .ctl_name       = CTL_NET,
 147                 .procname       = "net",
 148                 .mode           = 0555,
 149                 .child          = ipv4_table
 150         },
 151         { .ctl_name = 0 }
 152 };
 153
 154 static struct ctl_table_header * sysctl_header;
 155
 156 /*
 157  *      new/free a ip_vs_lblc_entry, which is a mapping of a destionation
 158  *      IP address to a server.
 159  */
 160 static inline struct ip_vs_lblc_entry *
 161 ip_vs_lblc_new(__u32 daddr, struct ip_vs_dest *dest)
 162 {
 163         struct ip_vs_lblc_entry *en;
 164
 165         en = kmalloc(sizeof(struct ip_vs_lblc_entry), GFP_ATOMIC);
 166         if (en == NULL) {
 167                 IP_VS_ERR("ip_vs_lblc_new(): no memory\n");
 168                 return NULL;
 169         }
 170
 171         INIT_LIST_HEAD(&en->list);
 172         en->addr = daddr;
 173
 174         atomic_inc(&dest->refcnt);
 175         en->dest = dest;
 176
 177         return en;
 178 }
 179
 180
 181 static inline void ip_vs_lblc_free(struct ip_vs_lblc_entry *en)
 182 {
 183         list_del(&en->list);
 184         /*
 185          * We don't kfree dest because it is refered either by its service
 186          * or the trash dest list.
 187          */
 188         atomic_dec(&en->dest->refcnt);
 189         kfree(en);
 190 }
 191
 192
 193 /*
 194  *      Returns hash value for IPVS LBLC entry
 195  */
 196 static inline unsigned ip_vs_lblc_hashkey(__u32 addr)
 197 {
 198         return (ntohl(addr)*2654435761UL) & IP_VS_LBLC_TAB_MASK;
 199 }
 200
 201
 202 /*
 203  *      Hash an entry in the ip_vs_lblc_table.
 204  *      returns bool success.
 205  */
 206 static int
 207 ip_vs_lblc_hash(struct ip_vs_lblc_table *tbl, struct ip_vs_lblc_entry *en)
 208 {
 209         unsigned hash;
 210
 211         if (!list_empty(&en->list)) {
 212                 IP_VS_ERR("ip_vs_lblc_hash(): request for already hashed, "
 213                           "called from %p\n", __builtin_return_address(0));
 214                 return 0;
 215         }
 216
 217         /*
 218          *      Hash by destination IP address
 219          */
 220         hash = ip_vs_lblc_hashkey(en->addr);
 221
 222         write_lock(&tbl->lock);
 223         list_add(&en->list, &tbl->bucket[hash]);
 224         atomic_inc(&tbl->entries);
 225         write_unlock(&tbl->lock);
 226
 227         return 1;
 228 }
 229
 230
 231 #if 0000
 232 /*
 233  *      Unhash ip_vs_lblc_entry from ip_vs_lblc_table.
 234  *      returns bool success.
 235  */
 236 static int ip_vs_lblc_unhash(struct ip_vs_lblc_table *tbl,
 237                              struct ip_vs_lblc_entry *en)
 238 {
 239         if (list_empty(&en->list)) {
 240                 IP_VS_ERR("ip_vs_lblc_unhash(): request for not hashed entry, "
 241                           "called from %p\n", __builtin_return_address(0));
 242                 return 0;
 243         }
 244
 245         /*
 246          * Remove it from the table
 247          */
 248         write_lock(&tbl->lock);
 249         list_del(&en->list);
 250         INIT_LIST_HEAD(&en->list);
 251         write_unlock(&tbl->lock);
 252
 253         return 1;
 254 }
 255 #endif
 256
 257
 258 /*
 259  *  Get ip_vs_lblc_entry associated with supplied parameters.
 260  */
 261 static inline struct ip_vs_lblc_entry *
 262 ip_vs_lblc_get(struct ip_vs_lblc_table *tbl, __u32 addr)
 263 {
 264         unsigned hash;
 265         struct ip_vs_lblc_entry *en;
 266
 267         hash = ip_vs_lblc_hashkey(addr);
 268
 269         read_lock(&tbl->lock);
 270
 271         list_for_each_entry(en, &tbl->bucket[hash], list) {
 272                 if (en->addr == addr) {
 273                         /* HIT */
 274                         read_unlock(&tbl->lock);
 275                         return en;
 276                 }
 277         }
 278
 279         read_unlock(&tbl->lock);
 280
 281         return NULL;
 282 }
 283
 284
 285 /*
 286  *      Flush all the entries of the specified table.
 287  */
 288 static void ip_vs_lblc_flush(struct ip_vs_lblc_table *tbl)
 289 {
 290         int i;
 291         struct ip_vs_lblc_entry *en, *nxt;
 292
 293         for (i=0; i<IP_VS_LBLC_TAB_SIZE; i++) {
 294                 write_lock(&tbl->lock);
 295                 list_for_each_entry_safe(en, nxt, &tbl->bucket[i], list) {
 296                         ip_vs_lblc_free(en);
 297                         atomic_dec(&tbl->entries);
 298                 }
 299                 write_unlock(&tbl->lock);
 300         }
 301 }
 302
 303
 304 static inline void ip_vs_lblc_full_check(struct ip_vs_lblc_table *tbl)
 305 {
 306         unsigned long now = jiffies;
 307         int i, j;
 308         struct ip_vs_lblc_entry *en, *nxt;
 309
 310         for (i=0, j=tbl->rover; i<IP_VS_LBLC_TAB_SIZE; i++) {
 311                 j = (j + 1) & IP_VS_LBLC_TAB_MASK;
 312
 313                 write_lock(&tbl->lock);
 314                 list_for_each_entry_safe(en, nxt, &tbl->bucket[j], list) {
 315                         if (time_before(now,
 316                                         en->lastuse + sysctl_ip_vs_lblc_expiration))
 317                                 continue;
 318
 319                         ip_vs_lblc_free(en);
 320                         atomic_dec(&tbl->entries);
 321                 }
 322                 write_unlock(&tbl->lock);
 323         }
 324         tbl->rover = j;
 325 }
 326
 327
 328 /*
 329  *      Periodical timer handler for IPVS lblc table
 330  *      It is used to collect stale entries when the number of entries
 331  *      exceeds the maximum size of the table.
 332  *
 333  *      Fixme: we probably need more complicated algorithm to collect
 334  *             entries that have not been used for a long time even
 335  *             if the number of entries doesn't exceed the maximum size
 336  *             of the table.
 337  *      The full expiration check is for this purpose now.
 338  */
 339 static void ip_vs_lblc_check_expire(unsigned long data)
 340 {
 341         struct ip_vs_lblc_table *tbl;
 342         unsigned long now = jiffies;
 343         int goal;
 344         int i, j;
 345         struct ip_vs_lblc_entry *en, *nxt;
 346
 347         tbl = (struct ip_vs_lblc_table *)data;
 348
 349         if ((tbl->counter % COUNT_FOR_FULL_EXPIRATION) == 0) {
 350                 /* do full expiration check */
 351                 ip_vs_lblc_full_check(tbl);
 352                 tbl->counter = 1;
 353                 goto out;
 354         }
 355
 356         if (atomic_read(&tbl->entries) <= tbl->max_size) {
 357                 tbl->counter++;
 358                 goto out;
 359         }
 360
 361         goal = (atomic_read(&tbl->entries) - tbl->max_size)*4/3;
 362         if (goal > tbl->max_size/2)
 363                 goal = tbl->max_size/2;
 364
 365         for (i=0, j=tbl->rover; i<IP_VS_LBLC_TAB_SIZE; i++) {
 366                 j = (j + 1) & IP_VS_LBLC_TAB_MASK;
 367
 368                 write_lock(&tbl->lock);
 369                 list_for_each_entry_safe(en, nxt, &tbl->bucket[j], list) {
 370                         if (time_before(now, en->lastuse + ENTRY_TIMEOUT))
 371                                 continue;
 372
 373                         ip_vs_lblc_free(en);
 374                         atomic_dec(&tbl->entries);
 375                         goal--;
 376                 }
 377                 write_unlock(&tbl->lock);
 378                 if (goal <= 0)
 379                         break;
 380         }
 381         tbl->rover = j;
 382
 383   out:
 384         mod_timer(&tbl->periodic_timer, jiffies+CHECK_EXPIRE_INTERVAL);
 385 }
 386
 387
 388 static int ip_vs_lblc_init_svc(struct ip_vs_service *svc)
 389 {
 390         int i;
 391         struct ip_vs_lblc_table *tbl;
 392
 393         /*
 394          *    Allocate the ip_vs_lblc_table for this service
 395          */
 396         tbl = kmalloc(sizeof(struct ip_vs_lblc_table), GFP_ATOMIC);
 397         if (tbl == NULL) {
 398                 IP_VS_ERR("ip_vs_lblc_init_svc(): no memory\n");
 399                 return -ENOMEM;
 400         }
 401         svc->sched_data = tbl;
 402         IP_VS_DBG(6, "LBLC hash table (memory=%Zdbytes) allocated for "
 403                   "current service\n",
 404                   sizeof(struct ip_vs_lblc_table));
 405
 406         /*
 407          *    Initialize the hash buckets
 408          */
 409         for (i=0; i<IP_VS_LBLC_TAB_SIZE; i++) {
 410                 INIT_LIST_HEAD(&tbl->bucket[i]);
 411         }
 412         rwlock_init(&tbl->lock);
 413         tbl->max_size = IP_VS_LBLC_TAB_SIZE*16;
 414         tbl->rover = 0;
 415         tbl->counter = 1;
 416
 417         /*
 418          *    Hook periodic timer for garbage collection
 419          */
 420         init_timer(&tbl->periodic_timer);
 421         tbl->periodic_timer.data = (unsigned long)tbl;
 422         tbl->periodic_timer.function = ip_vs_lblc_check_expire;
 423         tbl->periodic_timer.expires = jiffies+CHECK_EXPIRE_INTERVAL;
 424         add_timer(&tbl->periodic_timer);
 425
 426         return 0;
 427 }
 428
 429
 430 static int ip_vs_lblc_done_svc(struct ip_vs_service *svc)
 431 {
 432         struct ip_vs_lblc_table *tbl = svc->sched_data;
 433
 434         /* remove periodic timer */
 435         del_timer_sync(&tbl->periodic_timer);
 436
 437         /* got to clean up table entries here */
 438         ip_vs_lblc_flush(tbl);
 439
 440         /* release the table itself */
 441         kfree(svc->sched_data);
 442         IP_VS_DBG(6, "LBLC hash table (memory=%Zdbytes) released\n",
 443                   sizeof(struct ip_vs_lblc_table));
 444
 445         return 0;
 446 }
 447
 448
 449 static int ip_vs_lblc_update_svc(struct ip_vs_service *svc)
 450 {
 451         return 0;
 452 }
 453
 454
 455 static inline struct ip_vs_dest *
 456 __ip_vs_wlc_schedule(struct ip_vs_service *svc, struct iphdr *iph)
 457 {
 458         struct ip_vs_dest *dest, *least;
 459         int loh, doh;
 460
 461         /*
 462          * We think the overhead of processing active connections is fifty
 463          * times higher than that of inactive connections in average. (This
 464          * fifty times might not be accurate, we will change it later.) We
 465          * use the following formula to estimate the overhead:
 466          *                dest->activeconns*50 + dest->inactconns
 467          * and the load:
 468          *                (dest overhead) / dest->weight
 469          *
 470          * Remember -- no floats in kernel mode!!!
 471          * The comparison of h1*w2 > h2*w1 is equivalent to that of
 472          *                h1/w1 > h2/w2
 473          * if every weight is larger than zero.
 474          *
 475          * The server with weight=0 is quiesced and will not receive any
 476          * new connection.
 477          */
 478         list_for_each_entry(dest, &svc->destinations, n_list) {
 479                 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
 480                         continue;
 481                 if (atomic_read(&dest->weight) > 0) {
 482                         least = dest;
 483                         loh = atomic_read(&least->activeconns) * 50
 484                                 + atomic_read(&least->inactconns);
 485                         goto nextstage;
 486                 }
 487         }
 488         return NULL;
 489
 490         /*
 491          *    Find the destination with the least load.
 492          */
 493   nextstage:
 494         list_for_each_entry_continue(dest, &svc->destinations, n_list) {
 495                 if (dest->flags & IP_VS_DEST_F_OVERLOAD)
 496                         continue;
 497
 498                 doh = atomic_read(&dest->activeconns) * 50
 499                         + atomic_read(&dest->inactconns);
 500                 if (loh * atomic_read(&dest->weight) >
 501                     doh * atomic_read(&least->weight)) {
 502                         least = dest;
 503                         loh = doh;
 504                 }
 505         }
 506
 507         IP_VS_DBG(6, "LBLC: server %d.%d.%d.%d:%d "
 508                   "activeconns %d refcnt %d weight %d overhead %d\n",
 509                   NIPQUAD(least->addr), ntohs(least->port),
 510                   atomic_read(&least->activeconns),
 511                   atomic_read(&least->refcnt),
 512                   atomic_read(&least->weight), loh);
 513
 514         return least;
 515 }
 516
 517
 518 /*
 519  *   If this destination server is overloaded and there is a less loaded
 520  *   server, then return true.
 521  */
 522 static inline int
 523 is_overloaded(struct ip_vs_dest *dest, struct ip_vs_service *svc)
 524 {
 525         if (atomic_read(&dest->activeconns) > atomic_read(&dest->weight)) {
 526                 struct ip_vs_dest *d;
 527
 528                 list_for_each_entry(d, &svc->destinations, n_list) {
 529                         if (atomic_read(&d->activeconns)*2
 530                             < atomic_read(&d->weight)) {
 531                                 return 1;
 532                         }
 533                 }
 534         }
 535         return 0;
 536 }
 537
 538
 539 /*
 540  *    Locality-Based (weighted) Least-Connection scheduling
 541  */
 542 static struct ip_vs_dest *
 543 ip_vs_lblc_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
 544 {
 545         struct ip_vs_dest *dest;
 546         struct ip_vs_lblc_table *tbl;
 547         struct ip_vs_lblc_entry *en;
 548         struct iphdr *iph = skb->nh.iph;
 549
 550         IP_VS_DBG(6, "ip_vs_lblc_schedule(): Scheduling...\n");
 551
 552         tbl = (struct ip_vs_lblc_table *)svc->sched_data;
 553         en = ip_vs_lblc_get(tbl, iph->daddr);
 554         if (en == NULL) {
 555                 dest = __ip_vs_wlc_schedule(svc, iph);
 556                 if (dest == NULL) {
 557                         IP_VS_DBG(1, "no destination available\n");
 558                         return NULL;
 559                 }
 560                 en = ip_vs_lblc_new(iph->daddr, dest);
 561                 if (en == NULL) {
 562                         return NULL;
 563                 }
 564                 ip_vs_lblc_hash(tbl, en);
 565         } else {
 566                 dest = en->dest;
 567                 if (!(dest->flags & IP_VS_DEST_F_AVAILABLE)
 568                     || atomic_read(&dest->weight) <= 0
 569                     || is_overloaded(dest, svc)) {
 570                         dest = __ip_vs_wlc_schedule(svc, iph);
 571                         if (dest == NULL) {
 572                                 IP_VS_DBG(1, "no destination available\n");
 573                                 return NULL;
 574                         }
 575                         atomic_dec(&en->dest->refcnt);
 576                         atomic_inc(&dest->refcnt);
 577                         en->dest = dest;
 578                 }
 579         }
 580         en->lastuse = jiffies;
 581
 582         IP_VS_DBG(6, "LBLC: destination IP address %u.%u.%u.%u "
 583                   "--> server %u.%u.%u.%u:%d\n",
 584                   NIPQUAD(en->addr),
 585                   NIPQUAD(dest->addr),
 586                   ntohs(dest->port));
 587
 588         return dest;
 589 }
 590
 591
 592 /*
 593  *      IPVS LBLC Scheduler structure
 594  */
 595 static struct ip_vs_scheduler ip_vs_lblc_scheduler =
 596 {
 597         .name =                 "lblc",
 598         .refcnt =               ATOMIC_INIT(0),
 599         .module =               THIS_MODULE,
 600         .init_service =         ip_vs_lblc_init_svc,
 601         .done_service =         ip_vs_lblc_done_svc,
 602         .update_service =       ip_vs_lblc_update_svc,
 603         .schedule =             ip_vs_lblc_schedule,
 604 };
 605
 606
 607 static int __init ip_vs_lblc_init(void)
 608 {
 609         INIT_LIST_HEAD(&ip_vs_lblc_scheduler.n_list);
 610         sysctl_header = register_sysctl_table(lblc_root_table, 0);
 611         return register_ip_vs_scheduler(&ip_vs_lblc_scheduler);
 612 }
 613
 614
 615 static void __exit ip_vs_lblc_cleanup(void)
 616 {
 617         unregister_sysctl_table(sysctl_header);
 618         unregister_ip_vs_scheduler(&ip_vs_lblc_scheduler);
 619 }
 620
 621
 622 module_init(ip_vs_lblc_init);
 623 module_exit(ip_vs_lblc_cleanup);
 624 MODULE_LICENSE("GPL");