net/ipv4/ipvs/ip_vs_lblcr.c

   1 /*
   2  * IPVS:        Locality-Based Least-Connection with Replication scheduler
   3  *
   4  * Version:     $Id: ip_vs_lblcr.c,v 1.10 2002/03/25 12:44:35 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  *     Julian Anastasov        :    Added the missing (dest->weight>0)
  15  *                                  condition in the ip_vs_dest_set_max.
  16  *
  17  */
  18
  19 /*
  20  * The lblc/r algorithm is as follows (pseudo code):
  21  *
  22  *       if serverSet[dest_ip] is null then
  23  *               n, serverSet[dest_ip] <- {weighted least-conn node};
  24  *       else
  25  *               n <- {least-conn (alive) node in serverSet[dest_ip]};
  26  *               if (n is null) OR
  27  *                  (n.conns>n.weight AND
  28  *                   there is a node m with m.conns<m.weight/2) then
  29  *                   n <- {weighted least-conn node};
  30  *                   add n to serverSet[dest_ip];
  31  *               if |serverSet[dest_ip]| > 1 AND
  32  *                   now - serverSet[dest_ip].lastMod > T then
  33  *                   m <- {most conn node in serverSet[dest_ip]};
  34  *                   remove m from serverSet[dest_ip];
  35  *       if serverSet[dest_ip] changed then
  36  *               serverSet[dest_ip].lastMod <- now;
  37  *
  38  *       return n;
  39  *
  40  */
  41
  42 #include <linux/module.h>
  43 #include <linux/kernel.h>
  44
  45 /* for sysctl */
  46 #include <linux/fs.h>
  47 #include <linux/sysctl.h>
  48 /* for proc_net_create/proc_net_remove */
  49 #include <linux/proc_fs.h>
  50
  51 #include <net/ip_vs.h>
  52
  53
  54 /*
  55  *    It is for garbage collection of stale IPVS lblcr 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_lblcr_expiration = 24*60*60*HZ;
  69
  70
  71 /*
  72  *     for IPVS lblcr entry hash table
  73  */
  74 #ifndef CONFIG_IP_VS_LBLCR_TAB_BITS
  75 #define CONFIG_IP_VS_LBLCR_TAB_BITS      10
  76 #endif
  77 #define IP_VS_LBLCR_TAB_BITS     CONFIG_IP_VS_LBLCR_TAB_BITS
  78 #define IP_VS_LBLCR_TAB_SIZE     (1 << IP_VS_LBLCR_TAB_BITS)
  79 #define IP_VS_LBLCR_TAB_MASK     (IP_VS_LBLCR_TAB_SIZE - 1)
  80
  81
  82 /*
  83  *      IPVS destination set structure and operations
  84  */
  85 struct ip_vs_dest_list {
  86         struct ip_vs_dest_list  *next;          /* list link */
  87         struct ip_vs_dest       *dest;          /* destination server */
  88 };
  89
  90 struct ip_vs_dest_set {
  91         atomic_t                size;           /* set size */
  92         unsigned long           lastmod;        /* last modified time */
  93         struct ip_vs_dest_list  *list;          /* destination list */
  94         rwlock_t                lock;           /* lock for this list */
  95 };
  96
  97
  98 static struct ip_vs_dest_list *
  99 ip_vs_dest_set_insert(struct ip_vs_dest_set *set, struct ip_vs_dest *dest)
 100 {
 101         struct ip_vs_dest_list *e;
 102
 103         for (e=set->list; e!=NULL; e=e->next) {
 104                 if (e->dest == dest)
 105                         /* already existed */
 106                         return NULL;
 107         }
 108
 109         e = kmalloc(sizeof(struct ip_vs_dest_list), GFP_ATOMIC);
 110         if (e == NULL) {
 111                 IP_VS_ERR("ip_vs_dest_set_insert(): no memory\n");
 112                 return NULL;
 113         }
 114
 115         atomic_inc(&dest->refcnt);
 116         e->dest = dest;
 117
 118         /* link it to the list */
 119         write_lock(&set->lock);
 120         e->next = set->list;
 121         set->list = e;
 122         atomic_inc(&set->size);
 123         write_unlock(&set->lock);
 124
 125         set->lastmod = jiffies;
 126         return e;
 127 }
 128
 129 static void
 130 ip_vs_dest_set_erase(struct ip_vs_dest_set *set, struct ip_vs_dest *dest)
 131 {
 132         struct ip_vs_dest_list *e, **ep;
 133
 134         write_lock(&set->lock);
 135         for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {
 136                 if (e->dest == dest) {
 137                         /* HIT */
 138                         *ep = e->next;
 139                         atomic_dec(&set->size);
 140                         set->lastmod = jiffies;
 141                         atomic_dec(&e->dest->refcnt);
 142                         kfree(e);
 143                         break;
 144                 }
 145                 ep = &e->next;
 146         }
 147         write_unlock(&set->lock);
 148 }
 149
 150 static void ip_vs_dest_set_eraseall(struct ip_vs_dest_set *set)
 151 {
 152         struct ip_vs_dest_list *e, **ep;
 153
 154         write_lock(&set->lock);
 155         for (ep=&set->list, e=*ep; e!=NULL; e=*ep) {
 156                 *ep = e->next;
 157                 /*
 158                  * We don't kfree dest because it is refered either
 159                  * by its service or by the trash dest list.
 160                  */
 161                 atomic_dec(&e->dest->refcnt);
 162                 kfree(e);
 163         }
 164         write_unlock(&set->lock);
 165 }
 166
 167 /* get weighted least-connection node in the destination set */
 168 static inline struct ip_vs_dest *ip_vs_dest_set_min(struct ip_vs_dest_set *set)
 169 {
 170         register struct ip_vs_dest_list *e;
 171         struct ip_vs_dest *dest, *least;
 172         int loh, doh;
 173
 174         if (set == NULL)
 175                 return NULL;
 176
 177         read_lock(&set->lock);
 178         /* select the first destination server, whose weight > 0 */
 179         for (e=set->list; e!=NULL; e=e->next) {
 180                 least = e->dest;
 181                 if ((atomic_read(&least->weight) > 0)
 182                     && (least->flags & IP_VS_DEST_F_AVAILABLE)) {
 183                         loh = atomic_read(&least->activeconns) * 50
 184                                 + atomic_read(&least->inactconns);
 185                         goto nextstage;
 186                 }
 187         }
 188         read_unlock(&set->lock);
 189         return NULL;
 190
 191         /* find the destination with the weighted least load */
 192   nextstage:
 193         for (e=e->next; e!=NULL; e=e->next) {
 194                 dest = e->dest;
 195                 doh = atomic_read(&dest->activeconns) * 50
 196                         + atomic_read(&dest->inactconns);
 197                 if ((loh * atomic_read(&dest->weight) >
 198                      doh * atomic_read(&least->weight))
 199                     && (dest->flags & IP_VS_DEST_F_AVAILABLE)) {
 200                         least = dest;
 201                         loh = doh;
 202                 }
 203         }
 204         read_unlock(&set->lock);
 205
 206         IP_VS_DBG(6, "ip_vs_dest_set_min: server %d.%d.%d.%d:%d "
 207                   "activeconns %d refcnt %d weight %d overhead %d\n",
 208                   NIPQUAD(least->addr), ntohs(least->port),
 209                   atomic_read(&least->activeconns),
 210                   atomic_read(&least->refcnt),
 211                   atomic_read(&least->weight), loh);
 212         return least;
 213 }
 214
 215
 216 /* get weighted most-connection node in the destination set */
 217 static inline struct ip_vs_dest *ip_vs_dest_set_max(struct ip_vs_dest_set *set)
 218 {
 219         register struct ip_vs_dest_list *e;
 220         struct ip_vs_dest *dest, *most;
 221         int moh, doh;
 222
 223         if (set == NULL)
 224                 return NULL;
 225
 226         read_lock(&set->lock);
 227         /* select the first destination server, whose weight > 0 */
 228         for (e=set->list; e!=NULL; e=e->next) {
 229                 most = e->dest;
 230                 if (atomic_read(&most->weight) > 0) {
 231                         moh = atomic_read(&most->activeconns) * 50
 232                                 + atomic_read(&most->inactconns);
 233                         goto nextstage;
 234                 }
 235         }
 236         read_unlock(&set->lock);
 237         return NULL;
 238
 239         /* find the destination with the weighted most load */
 240   nextstage:
 241         for (e=e->next; e!=NULL; e=e->next) {
 242                 dest = e->dest;
 243                 doh = atomic_read(&dest->activeconns) * 50
 244                         + atomic_read(&dest->inactconns);
 245                 /* moh/mw < doh/dw ==> moh*dw < doh*mw, where mw,dw>0 */
 246                 if ((moh * atomic_read(&dest->weight) <
 247                      doh * atomic_read(&most->weight))
 248                     && (atomic_read(&dest->weight) > 0)) {
 249                         most = dest;
 250                         moh = doh;
 251                 }
 252         }
 253         read_unlock(&set->lock);
 254
 255         IP_VS_DBG(6, "ip_vs_dest_set_max: server %d.%d.%d.%d:%d "
 256                   "activeconns %d refcnt %d weight %d overhead %d\n",
 257                   NIPQUAD(most->addr), ntohs(most->port),
 258                   atomic_read(&most->activeconns),
 259                   atomic_read(&most->refcnt),
 260                   atomic_read(&most->weight), moh);
 261         return most;
 262 }
 263
 264
 265 /*
 266  *      IPVS lblcr entry represents an association between destination
 267  *      IP address and its destination server set
 268  */
 269 struct ip_vs_lblcr_entry {
 270         struct list_head        list;
 271         __u32                   addr;           /* destination IP address */
 272         struct ip_vs_dest_set   set;            /* destination server set */
 273         unsigned long           lastuse;        /* last used time */
 274 };
 275
 276
 277 /*
 278  *      IPVS lblcr hash table
 279  */
 280 struct ip_vs_lblcr_table {
 281         rwlock_t                lock;           /* lock for this table */
 282         struct list_head        bucket[IP_VS_LBLCR_TAB_SIZE];  /* hash bucket */
 283         atomic_t                entries;        /* number of entries */
 284         int                     max_size;       /* maximum size of entries */
 285         struct timer_list       periodic_timer; /* collect stale entries */
 286         int                     rover;          /* rover for expire check */
 287         int                     counter;        /* counter for no expire */
 288 };
 289
 290
 291 /*
 292  *      IPVS LBLCR sysctl table
 293  */
 294 struct ip_vs_lblcr_sysctl_table {
 295         struct ctl_table_header *sysctl_header;
 296         ctl_table vs_vars[2];
 297         ctl_table vs_dir[2];
 298         ctl_table ipv4_dir[2];
 299         ctl_table root_dir[2];
 300 };
 301
 302
 303 static struct ip_vs_lblcr_sysctl_table lblcr_sysctl_table = {
 304         NULL,
 305         {{NET_IPV4_VS_LBLCR_EXPIRE, "lblcr_expiration",
 306           &sysctl_ip_vs_lblcr_expiration,
 307           sizeof(int), 0644, NULL, &proc_dointvec_jiffies},
 308          {0}},
 309         {{NET_IPV4_VS, "vs", NULL, 0, 0555, lblcr_sysctl_table.vs_vars},
 310          {0}},
 311         {{NET_IPV4, "ipv4", NULL, 0, 0555, lblcr_sysctl_table.vs_dir},
 312          {0}},
 313         {{CTL_NET, "net", NULL, 0, 0555, lblcr_sysctl_table.ipv4_dir},
 314          {0}}
 315 };
 316
 317
 318 /*
 319  *      new/free a ip_vs_lblcr_entry, which is a mapping of a destination
 320  *      IP address to a server.
 321  */
 322 static inline struct ip_vs_lblcr_entry *ip_vs_lblcr_new(__u32 daddr)
 323 {
 324         struct ip_vs_lblcr_entry *en;
 325
 326         en = kmalloc(sizeof(struct ip_vs_lblcr_entry), GFP_ATOMIC);
 327         if (en == NULL) {
 328                 IP_VS_ERR("ip_vs_lblcr_new(): no memory\n");
 329                 return NULL;
 330         }
 331
 332         INIT_LIST_HEAD(&en->list);
 333         en->addr = daddr;
 334
 335         /* initilize its dest set */
 336         atomic_set(&(en->set.size), 0);
 337         en->set.list = NULL;
 338         en->set.lock = RW_LOCK_UNLOCKED;
 339
 340         return en;
 341 }
 342
 343
 344 static inline void ip_vs_lblcr_free(struct ip_vs_lblcr_entry *en)
 345 {
 346         list_del(&en->list);
 347         ip_vs_dest_set_eraseall(&en->set);
 348         kfree(en);
 349 }
 350
 351
 352 /*
 353  *      Returns hash value for IPVS LBLCR entry
 354  */
 355 static inline unsigned ip_vs_lblcr_hashkey(__u32 addr)
 356 {
 357         return (ntohl(addr)*2654435761UL) & IP_VS_LBLCR_TAB_MASK;
 358 }
 359
 360
 361 /*
 362  *      Hash an entry in the ip_vs_lblcr_table.
 363  *      returns bool success.
 364  */
 365 static int
 366 ip_vs_lblcr_hash(struct ip_vs_lblcr_table *tbl, struct ip_vs_lblcr_entry *en)
 367 {
 368         unsigned hash;
 369
 370         if (!list_empty(&en->list)) {
 371                 IP_VS_ERR("ip_vs_lblcr_hash(): request for already hashed, "
 372                           "called from %p\n", __builtin_return_address(0));
 373                 return 0;
 374         }
 375
 376         /*
 377          *      Hash by destination IP address
 378          */
 379         hash = ip_vs_lblcr_hashkey(en->addr);
 380
 381         write_lock(&tbl->lock);
 382         list_add(&en->list, &tbl->bucket[hash]);
 383         atomic_inc(&tbl->entries);
 384         write_unlock(&tbl->lock);
 385
 386         return 1;
 387 }
 388
 389
 390 #if 0000
 391 /*
 392  *      Unhash ip_vs_lblcr_entry from ip_vs_lblcr_table.
 393  *      returns bool success.
 394  */
 395 static int ip_vs_lblcr_unhash(struct ip_vs_lblcr_table *tbl,
 396                              struct ip_vs_lblcr_entry *en)
 397 {
 398         if (list_empty(&en->list)) {
 399                 IP_VS_ERR("ip_vs_lblcr_unhash(): request for not hashed entry, "
 400                           "called from %p\n", __builtin_return_address(0));
 401                 return 0;
 402         }
 403
 404         /*
 405          * Remove it from the table
 406          */
 407         write_lock(&tbl->lock);
 408         list_del(&en->list);
 409         INIT_LIST_HEAD(&en->list);
 410         write_unlock(&tbl->lock);
 411
 412         return 1;
 413 }
 414 #endif
 415
 416
 417 /*
 418  *  Get ip_vs_lblcr_entry associated with supplied parameters.
 419  */
 420 static inline struct ip_vs_lblcr_entry *
 421 ip_vs_lblcr_get(struct ip_vs_lblcr_table *tbl, __u32 addr)
 422 {
 423         unsigned hash;
 424         struct ip_vs_lblcr_entry *en;
 425         struct list_head *l,*e;
 426
 427         hash = ip_vs_lblcr_hashkey(addr);
 428         l = &tbl->bucket[hash];
 429
 430         read_lock(&tbl->lock);
 431
 432         for (e=l->next; e!=l; e=e->next) {
 433                 en = list_entry(e, struct ip_vs_lblcr_entry, list);
 434                 if (en->addr == addr) {
 435                         /* HIT */
 436                         read_unlock(&tbl->lock);
 437                         return en;
 438                 }
 439         }
 440
 441         read_unlock(&tbl->lock);
 442
 443         return NULL;
 444 }
 445
 446
 447 /*
 448  *      Flush all the entries of the specified table.
 449  */
 450 static void ip_vs_lblcr_flush(struct ip_vs_lblcr_table *tbl)
 451 {
 452         int i;
 453         struct list_head *l;
 454         struct ip_vs_lblcr_entry *en;
 455
 456         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
 457                 write_lock(&tbl->lock);
 458                 for (l=&tbl->bucket[i]; l->next!=l; ) {
 459                         en = list_entry(l->next,
 460                                         struct ip_vs_lblcr_entry, list);
 461                         ip_vs_lblcr_free(en);
 462                         atomic_dec(&tbl->entries);
 463                 }
 464                 write_unlock(&tbl->lock);
 465         }
 466 }
 467
 468
 469 static inline void ip_vs_lblcr_full_check(struct ip_vs_lblcr_table *tbl)
 470 {
 471         unsigned long now = jiffies;
 472         int i, j;
 473         struct list_head *l, *e;
 474         struct ip_vs_lblcr_entry *en;
 475
 476         for (i=0, j=tbl->rover; i<IP_VS_LBLCR_TAB_SIZE; i++) {
 477                 j = (j + 1) & IP_VS_LBLCR_TAB_MASK;
 478                 e = l = &tbl->bucket[j];
 479                 write_lock(&tbl->lock);
 480                 while (e->next != l) {
 481                         en = list_entry(e->next,
 482                                         struct ip_vs_lblcr_entry, list);
 483                         if ((now - en->lastuse) <
 484                             sysctl_ip_vs_lblcr_expiration) {
 485                                 e = e->next;
 486                                 continue;
 487                         }
 488                         ip_vs_lblcr_free(en);
 489                         atomic_dec(&tbl->entries);
 490                 }
 491                 write_unlock(&tbl->lock);
 492         }
 493         tbl->rover = j;
 494 }
 495
 496
 497 /*
 498  *      Periodical timer handler for IPVS lblcr table
 499  *      It is used to collect stale entries when the number of entries
 500  *      exceeds the maximum size of the table.
 501  *
 502  *      Fixme: we probably need more complicated algorithm to collect
 503  *             entries that have not been used for a long time even
 504  *             if the number of entries doesn't exceed the maximum size
 505  *             of the table.
 506  *      The full expiration check is for this purpose now.
 507  */
 508 static void ip_vs_lblcr_check_expire(unsigned long data)
 509 {
 510         struct ip_vs_lblcr_table *tbl;
 511         unsigned long now = jiffies;
 512         int goal;
 513         int i, j;
 514         struct list_head *l, *e;
 515         struct ip_vs_lblcr_entry *en;
 516
 517         tbl = (struct ip_vs_lblcr_table *)data;
 518
 519         if ((tbl->counter % COUNT_FOR_FULL_EXPIRATION) == 0) {
 520                 /* do full expiration check */
 521                 ip_vs_lblcr_full_check(tbl);
 522                 tbl->counter = 1;
 523                 goto out;
 524         }
 525
 526         if (atomic_read(&tbl->entries) <= tbl->max_size) {
 527                 tbl->counter++;
 528                 goto out;
 529         }
 530
 531         goal = (atomic_read(&tbl->entries) - tbl->max_size)*4/3;
 532         if (goal > tbl->max_size/2)
 533                 goal = tbl->max_size/2;
 534
 535         for (i=0, j=tbl->rover; i<IP_VS_LBLCR_TAB_SIZE; i++) {
 536                 j = (j + 1) & IP_VS_LBLCR_TAB_MASK;
 537                 e = l = &tbl->bucket[j];
 538                 write_lock(&tbl->lock);
 539                 while (e->next != l) {
 540                         en = list_entry(e->next,
 541                                         struct ip_vs_lblcr_entry, list);
 542                         if ((now - en->lastuse) < ENTRY_TIMEOUT) {
 543                                 e = e->next;
 544                                 continue;
 545                         }
 546                         ip_vs_lblcr_free(en);
 547                         atomic_dec(&tbl->entries);
 548                         goal--;
 549                 }
 550                 write_unlock(&tbl->lock);
 551                 if (goal <= 0)
 552                         break;
 553         }
 554         tbl->rover = j;
 555
 556   out:
 557         mod_timer(&tbl->periodic_timer, jiffies+CHECK_EXPIRE_INTERVAL);
 558 }
 559
 560
 561 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
 562 static struct ip_vs_lblcr_table *lblcr_table_list;
 563
 564 /*
 565  *      /proc/net/ip_vs_lblcr to display the mappings of
 566  *                  destination IP address <==> its serverSet
 567  */
 568 static int
 569 ip_vs_lblcr_getinfo(char *buffer, char **start, off_t offset, int length)
 570 {
 571         off_t pos=0, begin;
 572         int len=0, size;
 573         struct ip_vs_lblcr_table *tbl;
 574         unsigned long now = jiffies;
 575         int i;
 576         struct list_head *l, *e;
 577         struct ip_vs_lblcr_entry *en;
 578
 579         tbl = lblcr_table_list;
 580
 581         size = sprintf(buffer, "LastTime Dest IP address  Server set\n");
 582         pos += size;
 583         len += size;
 584
 585         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
 586                 l = &tbl->bucket[i];
 587                 read_lock_bh(&tbl->lock);
 588                 for (e=l->next; e!=l; e=e->next) {
 589                         char tbuf[16];
 590                         struct ip_vs_dest_list *d;
 591
 592                         en = list_entry(e, struct ip_vs_lblcr_entry, list);
 593                         sprintf(tbuf, "%u.%u.%u.%u", NIPQUAD(en->addr));
 594                         size = sprintf(buffer+len, "%8lu %-16s ",
 595                                        now-en->lastuse, tbuf);
 596
 597                         read_lock(&en->set.lock);
 598                         for (d=en->set.list; d!=NULL; d=d->next) {
 599                                 size += sprintf(buffer+len+size,
 600                                                 "%u.%u.%u.%u ",
 601                                                 NIPQUAD(d->dest->addr));
 602                         }
 603                         read_unlock(&en->set.lock);
 604                         size += sprintf(buffer+len+size, "\n");
 605                         len += size;
 606                         pos += size;
 607                         if (pos <= offset)
 608                                 len=0;
 609                         if (pos >= offset+length) {
 610                                 read_unlock_bh(&tbl->lock);
 611                                 goto done;
 612                         }
 613                 }
 614                 read_unlock_bh(&tbl->lock);
 615         }
 616
 617   done:
 618         begin = len - (pos - offset);
 619         *start = buffer + begin;
 620         len -= begin;
 621         if(len>length)
 622                 len = length;
 623         return len;
 624 }
 625 #endif
 626
 627
 628 static int ip_vs_lblcr_init_svc(struct ip_vs_service *svc)
 629 {
 630         int i;
 631         struct ip_vs_lblcr_table *tbl;
 632
 633         /*
 634          *    Allocate the ip_vs_lblcr_table for this service
 635          */
 636         tbl = kmalloc(sizeof(struct ip_vs_lblcr_table), GFP_ATOMIC);
 637         if (tbl == NULL) {
 638                 IP_VS_ERR("ip_vs_lblcr_init_svc(): no memory\n");
 639                 return -ENOMEM;
 640         }
 641         svc->sched_data = tbl;
 642         IP_VS_DBG(6, "LBLCR hash table (memory=%dbytes) allocated for "
 643                   "current service\n",
 644                   sizeof(struct ip_vs_lblcr_table));
 645
 646         /*
 647          *    Initialize the hash buckets
 648          */
 649         for (i=0; i<IP_VS_LBLCR_TAB_SIZE; i++) {
 650                 INIT_LIST_HEAD(&tbl->bucket[i]);
 651         }
 652         tbl->lock = RW_LOCK_UNLOCKED;
 653         tbl->max_size = IP_VS_LBLCR_TAB_SIZE*16;
 654         tbl->rover = 0;
 655         tbl->counter = 1;
 656
 657         /*
 658          *    Hook periodic timer for garbage collection
 659          */
 660         init_timer(&tbl->periodic_timer);
 661         tbl->periodic_timer.data = (unsigned long)tbl;
 662         tbl->periodic_timer.function = ip_vs_lblcr_check_expire;
 663         tbl->periodic_timer.expires = jiffies+CHECK_EXPIRE_INTERVAL;
 664         add_timer(&tbl->periodic_timer);
 665
 666 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
 667         lblcr_table_list = tbl;
 668 #endif
 669         return 0;
 670 }
 671
 672
 673 static int ip_vs_lblcr_done_svc(struct ip_vs_service *svc)
 674 {
 675         struct ip_vs_lblcr_table *tbl = svc->sched_data;
 676
 677         /* remove periodic timer */
 678         del_timer_sync(&tbl->periodic_timer);
 679
 680         /* got to clean up table entries here */
 681         ip_vs_lblcr_flush(tbl);
 682
 683         /* release the table itself */
 684         kfree(svc->sched_data);
 685         IP_VS_DBG(6, "LBLCR hash table (memory=%dbytes) released\n",
 686                   sizeof(struct ip_vs_lblcr_table));
 687
 688         return 0;
 689 }
 690
 691
 692 static int ip_vs_lblcr_update_svc(struct ip_vs_service *svc)
 693 {
 694         return 0;
 695 }
 696
 697
 698 static inline struct ip_vs_dest *
 699 __ip_vs_wlc_schedule(struct ip_vs_service *svc, struct iphdr *iph)
 700 {
 701         register struct list_head *l, *e;
 702         struct ip_vs_dest *dest, *least;
 703         int loh, doh;
 704
 705         /*
 706          * We think the overhead of processing active connections is fifty
 707          * times higher than that of inactive connections in average. (This
 708          * fifty times might not be accurate, we will change it later.) We
 709          * use the following formula to estimate the overhead:
 710          *                dest->activeconns*50 + dest->inactconns
 711          * and the load:
 712          *                (dest overhead) / dest->weight
 713          *
 714          * Remember -- no floats in kernel mode!!!
 715          * The comparison of h1*w2 > h2*w1 is equivalent to that of
 716          *                h1/w1 > h2/w2
 717          * if every weight is larger than zero.
 718          *
 719          * The server with weight=0 is quiesced and will not receive any
 720          * new connection.
 721          */
 722
 723         l = &svc->destinations;
 724         for (e=l->next; e!=l; e=e->next) {
 725                 least = list_entry(e, struct ip_vs_dest, n_list);
 726                 if (atomic_read(&least->weight) > 0) {
 727                         loh = atomic_read(&least->activeconns) * 50
 728                                 + atomic_read(&least->inactconns);
 729                         goto nextstage;
 730                 }
 731         }
 732         return NULL;
 733
 734         /*
 735          *    Find the destination with the least load.
 736          */
 737   nextstage:
 738         for (e=e->next; e!=l; e=e->next) {
 739                 dest = list_entry(e, struct ip_vs_dest, n_list);
 740                 doh = atomic_read(&dest->activeconns) * 50
 741                         + atomic_read(&dest->inactconns);
 742                 if (loh * atomic_read(&dest->weight) >
 743                     doh * atomic_read(&least->weight)) {
 744                         least = dest;
 745                         loh = doh;
 746                 }
 747         }
 748
 749         IP_VS_DBG(6, "LBLCR: server %d.%d.%d.%d:%d "
 750                   "activeconns %d refcnt %d weight %d overhead %d\n",
 751                   NIPQUAD(least->addr), ntohs(least->port),
 752                   atomic_read(&least->activeconns),
 753                   atomic_read(&least->refcnt),
 754                   atomic_read(&least->weight), loh);
 755
 756         return least;
 757 }
 758
 759
 760 /*
 761  *   If this destination server is overloaded and there is a less loaded
 762  *   server, then return true.
 763  */
 764 static inline int
 765 is_overloaded(struct ip_vs_dest *dest, struct ip_vs_service *svc)
 766 {
 767         if (atomic_read(&dest->activeconns) > atomic_read(&dest->weight)) {
 768                 register struct list_head *l, *e;
 769                 struct ip_vs_dest *d;
 770
 771                 l = &svc->destinations;
 772                 for (e=l->next; e!=l; e=e->next) {
 773                         d = list_entry(e, struct ip_vs_dest, n_list);
 774                         if (atomic_read(&d->activeconns)*2
 775                             < atomic_read(&d->weight)) {
 776                                 return 1;
 777                         }
 778                 }
 779         }
 780         return 0;
 781 }
 782
 783
 784 /*
 785  *    Locality-Based (weighted) Least-Connection scheduling
 786  */
 787 static struct ip_vs_dest *
 788 ip_vs_lblcr_schedule(struct ip_vs_service *svc, struct iphdr *iph)
 789 {
 790         struct ip_vs_dest *dest;
 791         struct ip_vs_lblcr_table *tbl;
 792         struct ip_vs_lblcr_entry *en;
 793
 794         IP_VS_DBG(6, "ip_vs_lblcr_schedule(): Scheduling...\n");
 795
 796         tbl = (struct ip_vs_lblcr_table *)svc->sched_data;
 797         en = ip_vs_lblcr_get(tbl, iph->daddr);
 798         if (en == NULL) {
 799                 dest = __ip_vs_wlc_schedule(svc, iph);
 800                 if (dest == NULL) {
 801                         IP_VS_DBG(1, "no destination available\n");
 802                         return NULL;
 803                 }
 804                 en = ip_vs_lblcr_new(iph->daddr);
 805                 if (en == NULL) {
 806                         return NULL;
 807                 }
 808                 ip_vs_dest_set_insert(&en->set, dest);
 809                 ip_vs_lblcr_hash(tbl, en);
 810         } else {
 811                 dest = ip_vs_dest_set_min(&en->set);
 812                 if (!dest || is_overloaded(dest, svc)) {
 813                         dest = __ip_vs_wlc_schedule(svc, iph);
 814                         if (dest == NULL) {
 815                                 IP_VS_DBG(1, "no destination available\n");
 816                                 return NULL;
 817                         }
 818                         ip_vs_dest_set_insert(&en->set, dest);
 819                 }
 820                 if (atomic_read(&en->set.size) > 1 &&
 821                     jiffies-en->set.lastmod > sysctl_ip_vs_lblcr_expiration) {
 822                         struct ip_vs_dest *m;
 823                         m = ip_vs_dest_set_max(&en->set);
 824                         if (m)
 825                                 ip_vs_dest_set_erase(&en->set, m);
 826                 }
 827         }
 828         en->lastuse = jiffies;
 829
 830         IP_VS_DBG(6, "LBLCR: destination IP address %u.%u.%u.%u "
 831                   "--> server %u.%u.%u.%u:%d\n",
 832                   NIPQUAD(en->addr),
 833                   NIPQUAD(dest->addr),
 834                   ntohs(dest->port));
 835
 836         return dest;
 837 }
 838
 839
 840 /*
 841  *      IPVS LBLCR Scheduler structure
 842  */
 843 static struct ip_vs_scheduler ip_vs_lblcr_scheduler =
 844 {
 845         {0},                     /* n_list */
 846         "lblcr",                 /* name */
 847         ATOMIC_INIT(0),          /* refcnt */
 848         THIS_MODULE,             /* this module */
 849         ip_vs_lblcr_init_svc,    /* service initializer */
 850         ip_vs_lblcr_done_svc,    /* service done */
 851         ip_vs_lblcr_update_svc,  /* service updater */
 852         ip_vs_lblcr_schedule,    /* select a server from the destination list */
 853 };
 854
 855
 856 static int __init ip_vs_lblcr_init(void)
 857 {
 858         INIT_LIST_HEAD(&ip_vs_lblcr_scheduler.n_list);
 859         lblcr_sysctl_table.sysctl_header =
 860                 register_sysctl_table(lblcr_sysctl_table.root_dir, 0);
 861 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
 862         proc_net_create("ip_vs_lblcr", 0, ip_vs_lblcr_getinfo);
 863 #endif
 864         return register_ip_vs_scheduler(&ip_vs_lblcr_scheduler);
 865 }
 866
 867
 868 static void __exit ip_vs_lblcr_cleanup(void)
 869 {
 870 #ifdef CONFIG_IP_VS_LBLCR_DEBUG
 871         proc_net_remove("ip_vs_lblcr");
 872 #endif
 873         unregister_sysctl_table(lblcr_sysctl_table.sysctl_header);
 874         unregister_ip_vs_scheduler(&ip_vs_lblcr_scheduler);
 875 }
 876
 877
 878 module_init(ip_vs_lblcr_init);
 879 module_exit(ip_vs_lblcr_cleanup);
 880 MODULE_LICENSE("GPL");