~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/ipv4/ipvs/ip_vs_dh.c

Version: ~ [ linux-5.15-rc5 ] ~ [ linux-5.14.11 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.72 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.152 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.210 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.250 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.286 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.288 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * IPVS:        Destination Hashing scheduling module
  3  *
  4  * Version:     $Id: ip_vs_dh.c,v 1.4 2001/10/19 15:05:17 wensong Exp $
  5  *
  6  * Authors:     Wensong Zhang <wensong@gnuchina.org>
  7  *
  8  *              Inspired by the consistent hashing scheduler patch from
  9  *              Thomas Proell <proellt@gmx.de>
 10  *
 11  *              This program is free software; you can redistribute it and/or
 12  *              modify it under the terms of the GNU General Public License
 13  *              as published by the Free Software Foundation; either version
 14  *              2 of the License, or (at your option) any later version.
 15  *
 16  * Changes:
 17  *
 18  */
 19 
 20 /*
 21  * The dh algorithm is to select server by the hash key of destination IP
 22  * address. The pseudo code is as follows:
 23  *
 24  *       n <- servernode[dest_ip];
 25  *       if (n is dead) OR
 26  *          (n is overloaded, such as n.conns>2*n.weight) then
 27  *                 return NULL;
 28  *
 29  *       return n;
 30  *
 31  * Notes that servernode is a 256-bucket hash table that maps the hash
 32  * index derived from packet destination IP address to the current server
 33  * array. If the dh scheduler is used in cache cluster, it is good to
 34  * combine it with cache_bypass feature. When the statically assigned
 35  * server is dead or overloaded, the load balancer can bypass the cache
 36  * server and send requests to the original server directly.
 37  *
 38  */
 39 
 40 #include <linux/module.h>
 41 #include <linux/kernel.h>
 42 
 43 #include <net/ip_vs.h>
 44 
 45 
 46 /*
 47  *      IPVS DH bucket
 48  */
 49 struct ip_vs_dh_bucket {
 50         struct ip_vs_dest       *dest;          /* real server (cache) */
 51 };
 52 
 53 /*
 54  *     for IPVS DH entry hash table
 55  */
 56 #ifndef CONFIG_IP_VS_DH_TAB_BITS
 57 #define CONFIG_IP_VS_DH_TAB_BITS        8
 58 #endif
 59 #define IP_VS_DH_TAB_BITS               CONFIG_IP_VS_DH_TAB_BITS
 60 #define IP_VS_DH_TAB_SIZE               (1 << IP_VS_DH_TAB_BITS)
 61 #define IP_VS_DH_TAB_MASK               (IP_VS_DH_TAB_SIZE - 1)
 62 
 63 
 64 /*
 65  *      Returns hash value for IPVS DH entry
 66  */
 67 static inline unsigned ip_vs_dh_hashkey(__u32 addr)
 68 {
 69         return (ntohl(addr)*2654435761UL) & IP_VS_DH_TAB_MASK;
 70 }
 71 
 72 
 73 /*
 74  *      Get ip_vs_dest associated with supplied parameters.
 75  */
 76 static inline struct ip_vs_dest *
 77 ip_vs_dh_get(struct ip_vs_dh_bucket *tbl, __u32 addr)
 78 {
 79         return (tbl[ip_vs_dh_hashkey(addr)]).dest;
 80 }
 81 
 82 
 83 /*
 84  *      Assign all the hash buckets of the specified table with the service.
 85  */
 86 static int
 87 ip_vs_dh_assign(struct ip_vs_dh_bucket *tbl, struct ip_vs_service *svc)
 88 {
 89         int i;
 90         struct ip_vs_dh_bucket *b;
 91         struct list_head *p;
 92         struct ip_vs_dest *dest;
 93 
 94         b = tbl;
 95         p = &svc->destinations;
 96         for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
 97                 if (list_empty(p)) {
 98                         b->dest = NULL;
 99                 } else {
100                         if (p == &svc->destinations)
101                                 p = p->next;
102 
103                         dest = list_entry(p, struct ip_vs_dest, n_list);
104                         atomic_inc(&dest->refcnt);
105                         b->dest = dest;
106 
107                         p = p->next;
108                 }
109                 b++;
110         }
111         return 0;
112 }
113 
114 
115 /*
116  *      Flush all the hash buckets of the specified table.
117  */
118 static void ip_vs_dh_flush(struct ip_vs_dh_bucket *tbl)
119 {
120         int i;
121         struct ip_vs_dh_bucket *b;
122 
123         b = tbl;
124         for (i=0; i<IP_VS_DH_TAB_SIZE; i++) {
125                 if (b->dest) {
126                         atomic_dec(&b->dest->refcnt);
127                         b->dest = NULL;
128                 }
129                 b++;
130         }
131 }
132 
133 
134 static int ip_vs_dh_init_svc(struct ip_vs_service *svc)
135 {
136         struct ip_vs_dh_bucket *tbl;
137 
138         /* allocate the DH table for this service */
139         tbl = kmalloc(sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE,
140                       GFP_ATOMIC);
141         if (tbl == NULL) {
142                 IP_VS_ERR("ip_vs_dh_init_svc(): no memory\n");
143                 return -ENOMEM;
144         }
145         svc->sched_data = tbl;
146         IP_VS_DBG(6, "DH hash table (memory=%dbytes) allocated for "
147                   "current service\n",
148                   sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
149 
150         /* assign the hash buckets with the updated service */
151         ip_vs_dh_assign(tbl, svc);
152 
153         return 0;
154 }
155 
156 
157 static int ip_vs_dh_done_svc(struct ip_vs_service *svc)
158 {
159         struct ip_vs_dh_bucket *tbl = svc->sched_data;
160 
161         /* got to clean up hash buckets here */
162         ip_vs_dh_flush(tbl);
163 
164         /* release the table itself */
165         kfree(svc->sched_data);
166         IP_VS_DBG(6, "DH hash table (memory=%dbytes) released\n",
167                   sizeof(struct ip_vs_dh_bucket)*IP_VS_DH_TAB_SIZE);
168 
169         return 0;
170 }
171 
172 
173 static int ip_vs_dh_update_svc(struct ip_vs_service *svc)
174 {
175         struct ip_vs_dh_bucket *tbl = svc->sched_data;
176 
177         /* got to clean up hash buckets here */
178         ip_vs_dh_flush(tbl);
179 
180         /* assign the hash buckets with the updated service */
181         ip_vs_dh_assign(tbl, svc);
182 
183         return 0;
184 }
185 
186 
187 /*
188  *      If the number of active connections is twice larger than its weight,
189  *      consider that the server is overloaded here.
190  */
191 static inline int is_overloaded(struct ip_vs_dest *dest)
192 {
193         if (atomic_read(&dest->activeconns) > atomic_read(&dest->weight)*2) {
194                 return 1;
195         }
196         return 0;
197 }
198 
199 
200 /*
201  *      Destination hashing scheduling
202  */
203 static struct ip_vs_dest *
204 ip_vs_dh_schedule(struct ip_vs_service *svc, struct iphdr *iph)
205 {
206         struct ip_vs_dest *dest;
207         struct ip_vs_dh_bucket *tbl;
208 
209         IP_VS_DBG(6, "ip_vs_dh_schedule(): Scheduling...\n");
210 
211         tbl = (struct ip_vs_dh_bucket *)svc->sched_data;
212         dest = ip_vs_dh_get(tbl, iph->daddr);
213         if (!dest
214             || !(dest->flags & IP_VS_DEST_F_AVAILABLE)
215             || atomic_read(&dest->weight) <= 0
216             || is_overloaded(dest)) {
217                 return NULL;
218         }
219 
220         IP_VS_DBG(6, "DH: destination IP address %u.%u.%u.%u "
221                   "--> server %u.%u.%u.%u:%d\n",
222                   NIPQUAD(iph->daddr),
223                   NIPQUAD(dest->addr),
224                   ntohs(dest->port));
225 
226         return dest;
227 }
228 
229 
230 /*
231  *      IPVS DH Scheduler structure
232  */
233 static struct ip_vs_scheduler ip_vs_dh_scheduler =
234 {
235         {0},                    /* n_list */
236         "dh",                   /* name */
237         ATOMIC_INIT(0),         /* refcnt */
238         THIS_MODULE,            /* this module */
239         ip_vs_dh_init_svc,      /* service initializer */
240         ip_vs_dh_done_svc,      /* service done */
241         ip_vs_dh_update_svc,    /* service updater */
242         ip_vs_dh_schedule,      /* select a server from the destination list */
243 };
244 
245 
246 static int __init ip_vs_dh_init(void)
247 {
248         INIT_LIST_HEAD(&ip_vs_dh_scheduler.n_list);
249         return register_ip_vs_scheduler(&ip_vs_dh_scheduler);
250 }
251 
252 
253 static void __exit ip_vs_dh_cleanup(void)
254 {
255         unregister_ip_vs_scheduler(&ip_vs_dh_scheduler);
256 }
257 
258 
259 module_init(ip_vs_dh_init);
260 module_exit(ip_vs_dh_cleanup);
261 MODULE_LICENSE("GPL");
262 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp