Main Page | Class List | File List | Class Members | File Members

inetpeer.c File Reference

#include <linux/types.h>
#include <linux/slab.h>
#include <linux/interrupt.h>
#include <linux/spinlock.h>
#include <linux/random.h>
#include <linux/sched.h>
#include <linux/timer.h>
#include <linux/time.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <net/inetpeer.h>

Go to the source code of this file.

Defines

#define node_height(x)   x->avl_height
#define peer_avl_empty   (&peer_fake_node)
#define PEER_MAXDEPTH   40
#define PEER_MAX_CLEANUP_WORK   30
#define lookup(daddr)
#define lookup_rightempty(start)
#define link_to_pool(n)

Functions

void peer_check_expire (unsigned long dummy)
void __init inet_initpeers (void)
void unlink_from_unused (struct inet_peer *p)
void peer_avl_rebalance (struct inet_peer **stack[], struct inet_peer ***stackend)
void unlink_from_pool (struct inet_peer *p)
int cleanup_once (unsigned long ttl)
inet_peer * inet_getpeer (__u32 daddr, int create)

Variables

spinlock_t inet_peer_idlock = SPIN_LOCK_UNLOCKED
kmem_cache_t * peer_cachep
inet_peer peer_fake_node
inet_peer * peer_root = peer_avl_empty
rwlock_t peer_pool_lock = RW_LOCK_UNLOCKED
volatile int peer_total
int inet_peer_threshold = 65536 + 128
int inet_peer_minttl = 120 * HZ
int inet_peer_maxttl = 10 * 60 * HZ
inet_peer * inet_peer_unused_head
inet_peer ** inet_peer_unused_tailp = &inet_peer_unused_head
spinlock_t inet_peer_unused_lock = SPIN_LOCK_UNLOCKED
timer_list peer_periodic_timer
int inet_peer_gc_mintime

Define Documentation

#define link_to_pool (  n   ) 
 

Value:

do {                                                            \
        n->avl_height = 1;                                      \
        n->avl_left = peer_avl_empty;                           \
        n->avl_right = peer_avl_empty;                          \
        **--stackptr = n;                                       \
        peer_avl_rebalance(stack, stackptr);                    \
} while(0)
Definition at line 267 of file inetpeer.c.

Referenced by inet_getpeer().

#define lookup (  daddr   ) 
 

Value:

({                                                              \
        struct inet_peer *u, **v;                               \
        stackptr = stack;                                       \
        *stackptr++ = &peer_root;                               \
        for (u = peer_root; u != peer_avl_empty; ) {            \
                if (daddr == u->v4daddr)                        \
                        break;                                  \
                if (daddr < u->v4daddr)                         \
                        v = &u->avl_left;                       \
                else                                            \
                        v = &u->avl_right;                      \
                *stackptr++ = v;                                \
                u = *v;                                         \
        }                                                       \
        u;                                                      \
})
Definition at line 156 of file inetpeer.c.

Referenced by inet_getpeer(), and unlink_from_pool().

#define lookup_rightempty (  start   ) 
 

Value:

({                                                              \
        struct inet_peer *u, **v;                               \
        *stackptr++ = &start->avl_left;                         \
        v = &start->avl_left;                                   \
        for (u = *v; u->avl_right != peer_avl_empty; ) {        \
                v = &u->avl_right;                              \
                *stackptr++ = v;                                \
                u = *v;                                         \
        }                                                       \
        u;                                                      \
})
Definition at line 175 of file inetpeer.c.

Referenced by unlink_from_pool().

#define node_height (  x   )     x->avl_height
 

Definition at line 75 of file inetpeer.c.

Referenced by peer_avl_rebalance().

#define peer_avl_empty   (&peer_fake_node)
 

Definition at line 81 of file inetpeer.c.

Referenced by inet_getpeer(), and unlink_from_pool().

#define PEER_MAX_CLEANUP_WORK   30
 

Definition at line 97 of file inetpeer.c.

Referenced by peer_check_expire().

#define PEER_MAXDEPTH   40
 

Definition at line 84 of file inetpeer.c.

Referenced by inet_getpeer(), and unlink_from_pool().

Function Documentation

int cleanup_once (  unsigned long  ttl  )  [static]
 

Definition at line 335 of file inetpeer.c.

References inet_peer_unused_head, inet_peer_unused_lock, inet_peer_unused_tailp, unlink_from_pool(), inet_peer::unused_next, and inet_peer::unused_prevp.

Referenced by inet_getpeer(), and peer_check_expire().

00336 {
00337         struct inet_peer *p;
00338 
00339         /* Remove the first entry from the list of unused nodes. */
00340         spin_lock_bh(&inet_peer_unused_lock);
00341         p = inet_peer_unused_head;
00342         if (p != NULL) {
00343                 if (time_after(p->dtime + ttl, jiffies)) {
00344                         /* Do not prune fresh entries. */
00345                         spin_unlock_bh(&inet_peer_unused_lock);
00346                         return -1;
00347                 }
00348                 inet_peer_unused_head = p->unused_next;
00349                 if (p->unused_next != NULL)
00350                         p->unused_next->unused_prevp = p->unused_prevp;
00351                 else
00352                         inet_peer_unused_tailp = p->unused_prevp;
00353                 p->unused_prevp = NULL; /* mark as not on the list */
00354                 /* Grab an extra reference to prevent node disappearing
00355                  * before unlink_from_pool() call. */
00356                 atomic_inc(&p->refcnt);
00357         }
00358         spin_unlock_bh(&inet_peer_unused_lock);
00359 
00360         if (p == NULL)
00361                 /* It means that the total number of USED entries has
00362                  * grown over inet_peer_threshold.  It shouldn't really
00363                  * happen because of entry limits in route cache. */
00364                 return -1;
00365 
00366         unlink_from_pool(p);
00367         return 0;
00368 }

struct inet_peer* inet_getpeer (  __u32  daddr,
int  create
) 
 

Definition at line 371 of file inetpeer.c.

References cleanup_once(), inet_peer_threshold, link_to_pool, lookup, peer_avl_empty, peer_cachep, PEER_MAXDEPTH, peer_pool_lock, peer_total, and unlink_from_unused().

Referenced by rt_bind_peer(), tcp_v4_remember_stamp(), and tcp_v4_tw_remember_stamp().

00372 {
00373         struct inet_peer *p, *n;
00374         struct inet_peer **stack[PEER_MAXDEPTH], ***stackptr;
00375 
00376         /* Look up for the address quickly. */
00377         read_lock_bh(&peer_pool_lock);
00378         p = lookup(daddr);
00379         if (p != peer_avl_empty)
00380                 atomic_inc(&p->refcnt);
00381         read_unlock_bh(&peer_pool_lock);
00382 
00383         if (p != peer_avl_empty) {
00384                 /* The existing node has been found. */
00385                 /* Remove the entry from unused list if it was there. */
00386                 unlink_from_unused(p);
00387                 return p;
00388         }
00389 
00390         if (!create)
00391                 return NULL;
00392 
00393         /* Allocate the space outside the locked region. */
00394         n = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
00395         if (n == NULL)
00396                 return NULL;
00397         n->v4daddr = daddr;
00398         atomic_set(&n->refcnt, 1);
00399         n->ip_id_count = secure_ip_id(daddr);
00400         n->tcp_ts_stamp = 0;
00401 
00402         write_lock_bh(&peer_pool_lock);
00403         /* Check if an entry has suddenly appeared. */
00404         p = lookup(daddr);
00405         if (p != peer_avl_empty)
00406                 goto out_free;
00407 
00408         /* Link the node. */
00409         link_to_pool(n);
00410         n->unused_prevp = NULL; /* not on the list */
00411         peer_total++;
00412         write_unlock_bh(&peer_pool_lock);
00413 
00414         if (peer_total >= inet_peer_threshold)
00415                 /* Remove one less-recently-used entry. */
00416                 cleanup_once(0);
00417 
00418         return n;
00419 
00420 out_free:
00421         /* The appropriate node is already in the pool. */
00422         atomic_inc(&p->refcnt);
00423         write_unlock_bh(&peer_pool_lock);
00424         /* Remove the entry from unused list if it was there. */
00425         unlink_from_unused(p);
00426         /* Free preallocated the preallocated node. */
00427         kmem_cache_free(peer_cachep, n);
00428         return p;
00429 }

void __init inet_initpeers (  void   ) 
 

Definition at line 108 of file inetpeer.c.

References inet_peer_gc_maxtime, inet_peer_threshold, net_random(), peer_cachep, and peer_periodic_timer.

Referenced by ip_init().

00109 {
00110         struct sysinfo si;
00111 
00112         /* Use the straight interface to information about memory. */
00113         si_meminfo(&si);
00114         /* The values below were suggested by Alexey Kuznetsov
00115          * <kuznet@ms2.inr.ac.ru>.  I don't have any opinion about the values
00116          * myself.  --SAW
00117          */
00118         if (si.totalram <= (32768*1024)/PAGE_SIZE)
00119                 inet_peer_threshold >>= 1; /* max pool size about 1MB on IA32 */
00120         if (si.totalram <= (16384*1024)/PAGE_SIZE)
00121                 inet_peer_threshold >>= 1; /* about 512KB */
00122         if (si.totalram <= (8192*1024)/PAGE_SIZE)
00123                 inet_peer_threshold >>= 2; /* about 128KB */
00124 
00125         peer_cachep = kmem_cache_create("inet_peer_cache",
00126                         sizeof(struct inet_peer),
00127                         0, SLAB_HWCACHE_ALIGN,
00128                         NULL, NULL);
00129 
00130         /* All the timers, started at system startup tend
00131            to synchronize. Perturb it a bit.
00132          */
00133         peer_periodic_timer.expires = jiffies
00134                 + net_random() % inet_peer_gc_maxtime
00135                 + inet_peer_gc_maxtime;
00136         add_timer(&peer_periodic_timer);
00137 }

void peer_avl_rebalance (  struct inet_peer **  stack[],
struct inet_peer ***  stackend
)  [static]
 

Definition at line 191 of file inetpeer.c.

References inet_peer::avl_left, inet_peer::avl_right, and node_height.

Referenced by unlink_from_pool().

00193 {
00194         struct inet_peer **nodep, *node, *l, *r;
00195         int lh, rh;
00196 
00197         while (stackend > stack) {
00198                 nodep = *--stackend;
00199                 node = *nodep;
00200                 l = node->avl_left;
00201                 r = node->avl_right;
00202                 lh = node_height(l);
00203                 rh = node_height(r);
00204                 if (lh > rh + 1) { /* l: RH+2 */
00205                         struct inet_peer *ll, *lr, *lrl, *lrr;
00206                         int lrh;
00207                         ll = l->avl_left;
00208                         lr = l->avl_right;
00209                         lrh = node_height(lr);
00210                         if (lrh <= node_height(ll)) {   /* ll: RH+1 */
00211                                 node->avl_left = lr;    /* lr: RH or RH+1 */
00212                                 node->avl_right = r;    /* r: RH */
00213                                 node->avl_height = lrh + 1; /* RH+1 or RH+2 */
00214                                 l->avl_left = ll;       /* ll: RH+1 */
00215                                 l->avl_right = node;    /* node: RH+1 or RH+2 */
00216                                 l->avl_height = node->avl_height + 1;
00217                                 *nodep = l;
00218                         } else { /* ll: RH, lr: RH+1 */
00219                                 lrl = lr->avl_left;     /* lrl: RH or RH-1 */
00220                                 lrr = lr->avl_right;    /* lrr: RH or RH-1 */
00221                                 node->avl_left = lrr;   /* lrr: RH or RH-1 */
00222                                 node->avl_right = r;    /* r: RH */
00223                                 node->avl_height = rh + 1; /* node: RH+1 */
00224                                 l->avl_left = ll;       /* ll: RH */
00225                                 l->avl_right = lrl;     /* lrl: RH or RH-1 */
00226                                 l->avl_height = rh + 1; /* l: RH+1 */
00227                                 lr->avl_left = l;       /* l: RH+1 */
00228                                 lr->avl_right = node;   /* node: RH+1 */
00229                                 lr->avl_height = rh + 2;
00230                                 *nodep = lr;
00231                         }
00232                 } else if (rh > lh + 1) { /* r: LH+2 */
00233                         struct inet_peer *rr, *rl, *rlr, *rll;
00234                         int rlh;
00235                         rr = r->avl_right;
00236                         rl = r->avl_left;
00237                         rlh = node_height(rl);
00238                         if (rlh <= node_height(rr)) {   /* rr: LH+1 */
00239                                 node->avl_right = rl;   /* rl: LH or LH+1 */
00240                                 node->avl_left = l;     /* l: LH */
00241                                 node->avl_height = rlh + 1; /* LH+1 or LH+2 */
00242                                 r->avl_right = rr;      /* rr: LH+1 */
00243                                 r->avl_left = node;     /* node: LH+1 or LH+2 */
00244                                 r->avl_height = node->avl_height + 1;
00245                                 *nodep = r;
00246                         } else { /* rr: RH, rl: RH+1 */
00247                                 rlr = rl->avl_right;    /* rlr: LH or LH-1 */
00248                                 rll = rl->avl_left;     /* rll: LH or LH-1 */
00249                                 node->avl_right = rll;  /* rll: LH or LH-1 */
00250                                 node->avl_left = l;     /* l: LH */
00251                                 node->avl_height = lh + 1; /* node: LH+1 */
00252                                 r->avl_right = rr;      /* rr: LH */
00253                                 r->avl_left = rlr;      /* rlr: LH or LH-1 */
00254                                 r->avl_height = lh + 1; /* r: LH+1 */
00255                                 rl->avl_right = r;      /* r: LH+1 */
00256                                 rl->avl_left = node;    /* node: LH+1 */
00257                                 rl->avl_height = lh + 2;
00258                                 *nodep = rl;
00259                         }
00260                 } else {
00261                         node->avl_height = (lh > rh ? lh : rh) + 1;
00262                 }
00263         }
00264 }

void peer_check_expire (  unsigned long  dummy  )  [static]
 

Definition at line 432 of file inetpeer.c.

References cleanup_once(), inet_peer_gc_maxtime, inet_peer_gc_mintime, inet_peer_maxttl, inet_peer_minttl, inet_peer_threshold, PEER_MAX_CLEANUP_WORK, peer_periodic_timer, and peer_total.

00433 {
00434         int i;
00435         int ttl;
00436 
00437         if (peer_total >= inet_peer_threshold)
00438                 ttl = inet_peer_minttl;
00439         else
00440                 ttl = inet_peer_maxttl
00441                                 - (inet_peer_maxttl - inet_peer_minttl) / HZ *
00442                                         peer_total / inet_peer_threshold * HZ;
00443         for (i = 0; i < PEER_MAX_CLEANUP_WORK && !cleanup_once(ttl); i++);
00444 
00445         /* Trigger the timer after inet_peer_gc_mintime .. inet_peer_gc_maxtime
00446          * interval depending on the total number of entries (more entries,
00447          * less interval). */
00448         peer_periodic_timer.expires = jiffies
00449                 + inet_peer_gc_maxtime
00450                 - (inet_peer_gc_maxtime - inet_peer_gc_mintime) / HZ *
00451                         peer_total / inet_peer_threshold * HZ;
00452         add_timer(&peer_periodic_timer);
00453 }

void unlink_from_pool (  struct inet_peer *  p  )  [static]
 

Definition at line 277 of file inetpeer.c.

References inet_peer::avl_height, inet_peer::avl_left, inet_peer::avl_right, inet_putpeer(), lookup, lookup_rightempty, peer_avl_empty, peer_avl_rebalance(), peer_cachep, PEER_MAXDEPTH, peer_pool_lock, peer_total, inet_peer::refcnt, and inet_peer::v4daddr.

Referenced by cleanup_once().

00278 {
00279         int do_free;
00280 
00281         do_free = 0;
00282 
00283         write_lock_bh(&peer_pool_lock);
00284         /* Check the reference counter.  It was artificially incremented by 1
00285          * in cleanup() function to prevent sudden disappearing.  If the
00286          * reference count is still 1 then the node is referenced only as `p'
00287          * here and from the pool.  So under the exclusive pool lock it's safe
00288          * to remove the node and free it later. */
00289         if (atomic_read(&p->refcnt) == 1) {
00290                 struct inet_peer **stack[PEER_MAXDEPTH];
00291                 struct inet_peer ***stackptr, ***delp;
00292                 if (lookup(p->v4daddr) != p)
00293                         BUG();
00294                 delp = stackptr - 1; /* *delp[0] == p */
00295                 if (p->avl_left == peer_avl_empty) {
00296                         *delp[0] = p->avl_right;
00297                         --stackptr;
00298                 } else {
00299                         /* look for a node to insert instead of p */
00300                         struct inet_peer *t;
00301                         t = lookup_rightempty(p);
00302                         if (*stackptr[-1] != t)
00303                                 BUG();
00304                         **--stackptr = t->avl_left;
00305                         /* t is removed, t->v4daddr > x->v4daddr for any
00306                          * x in p->avl_left subtree.
00307                          * Put t in the old place of p. */
00308                         *delp[0] = t;
00309                         t->avl_left = p->avl_left;
00310                         t->avl_right = p->avl_right;
00311                         t->avl_height = p->avl_height;
00312                         if (delp[1] != &p->avl_left)
00313                                 BUG();
00314                         delp[1] = &t->avl_left; /* was &p->avl_left */
00315                 }
00316                 peer_avl_rebalance(stack, stackptr);
00317                 peer_total--;
00318                 do_free = 1;
00319         }
00320         write_unlock_bh(&peer_pool_lock);
00321 
00322         if (do_free)
00323                 kmem_cache_free(peer_cachep, p);
00324         else
00325                 /* The node is used again.  Decrease the reference counter
00326                  * back.  The loop "cleanup -> unlink_from_unused
00327                  *   -> unlink_from_pool -> putpeer -> link_to_unused
00328                  *   -> cleanup (for the same node)"
00329                  * doesn't really exist because the entry will have a
00330                  * recent deletion time and will not be cleaned again soon. */
00331                 inet_putpeer(p);
00332 }

void unlink_from_unused (  struct inet_peer *  p  )  [static]
 

Definition at line 140 of file inetpeer.c.

References inet_peer_unused_lock, inet_peer_unused_tailp, inet_peer::unused_next, and inet_peer::unused_prevp.

Referenced by inet_getpeer().

00141 {
00142         spin_lock_bh(&inet_peer_unused_lock);
00143         if (p->unused_prevp != NULL) {
00144                 /* On unused list. */
00145                 *p->unused_prevp = p->unused_next;
00146                 if (p->unused_next != NULL)
00147                         p->unused_next->unused_prevp = p->unused_prevp;
00148                 else
00149                         inet_peer_unused_tailp = p->unused_prevp;
00150                 p->unused_prevp = NULL; /* mark it as removed */
00151         }
00152         spin_unlock_bh(&inet_peer_unused_lock);
00153 }

Variable Documentation

int inet_peer_gc_mintime
 

Initial value:

 10 * HZ
    inet_peer_gc_maxtime = 120 * HZ
Definition at line 104 of file inetpeer.c.

Referenced by peer_check_expire().

spinlock_t inet_peer_idlock = SPIN_LOCK_UNLOCKED
 

Definition at line 71 of file inetpeer.c.

Referenced by inet_getid().

int inet_peer_maxttl = 10 * 60 * HZ
 

Definition at line 91 of file inetpeer.c.

Referenced by peer_check_expire().

int inet_peer_minttl = 120 * HZ
 

Definition at line 90 of file inetpeer.c.

Referenced by peer_check_expire().

int inet_peer_threshold = 65536 + 128
 

Definition at line 88 of file inetpeer.c.

Referenced by inet_getpeer(), inet_initpeers(), and peer_check_expire().

struct inet_peer* inet_peer_unused_head
 

Definition at line 94 of file inetpeer.c.

Referenced by cleanup_once().

spinlock_t inet_peer_unused_lock = SPIN_LOCK_UNLOCKED
 

Definition at line 96 of file inetpeer.c.

Referenced by cleanup_once(), inet_putpeer(), and unlink_from_unused().

struct inet_peer ** inet_peer_unused_tailp = &inet_peer_unused_head
 

Definition at line 95 of file inetpeer.c.

Referenced by cleanup_once(), inet_putpeer(), and unlink_from_unused().

kmem_cache_t* peer_cachep [static]
 

Definition at line 73 of file inetpeer.c.

Referenced by inet_getpeer(), inet_initpeers(), and unlink_from_pool().

struct inet_peer peer_fake_node [static]
 

Initial value:

 {
        avl_left : &peer_fake_node,
        avl_right : &peer_fake_node,
        avl_height : 0
}
Definition at line 76 of file inetpeer.c.

struct timer_list peer_periodic_timer [static]
 

Initial value:


        { { NULL, NULL }, 0, 0, &peer_check_expire }
Definition at line 100 of file inetpeer.c.

Referenced by inet_initpeers(), and peer_check_expire().

rwlock_t peer_pool_lock = RW_LOCK_UNLOCKED [static]
 

Definition at line 83 of file inetpeer.c.

Referenced by inet_getpeer(), and unlink_from_pool().

struct inet_peer* peer_root = peer_avl_empty [static]
 

Definition at line 82 of file inetpeer.c.

volatile int peer_total [static]
 

Definition at line 86 of file inetpeer.c.

Referenced by inet_getpeer(), peer_check_expire(), and unlink_from_pool().

Generated on Wed Dec 1 21:25:35 2004 for Linux 2.4.23 Networking by doxygen 1.3.8