net/cor/snd.c

   1 /*
   2  *      Connection oriented routing
   3  *      Copyright (C) 2007-2008 Michael Blizek
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      as published by the Free Software Foundation; either version 2
   8  *      of the License, or (at your option) any later version.
   9  *
  10  *      This program is distributed in the hope that it will be useful,
  11  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *      GNU General Public License for more details.
  14  *
  15  *      You should have received a copy of the GNU General Public License
  16  *      along with this program; if not, write to the Free Software
  17  *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18  *      02110-1301, USA.
  19  */
  20
  21 #include <linux/gfp.h>
  22 #include <linux/jiffies.h>
  23 #include <linux/slab.h>
  24
  25 #include "cor.h"
  26
  27 struct kmem_cache *connretrans_slab;
  28
  29 struct conn_retrans {
  30         /* timeout_list and conn_list share a single ref */
  31         struct kref ref;
  32         struct list_head timeout_list;
  33         struct list_head conn_list;
  34         struct htab_entry htab_entry;
  35         struct conn *rconn;
  36         __u32 seqno;
  37         __u32 length;
  38         __u8 ackrcvd;
  39         unsigned long timeout;
  40 };
  41
  42 static void free_connretrans(struct kref *ref)
  43 {
  44         struct conn_retrans *cr = container_of(ref, struct conn_retrans, ref);
  45         kmem_cache_free(connretrans_slab, cr);
  46         kref_put(&(cr->rconn->ref), free_conn);
  47 }
  48
  49 static struct htable retransmits_conn;
  50
  51 struct retransmit_matchparam {
  52         struct neighbor *nb;
  53         __u32 conn_id;
  54         __u32 seqno;
  55 };
  56
  57 static __u32 rm_to_key(struct retransmit_matchparam *rm)
  58 {
  59         return rm->conn_id ^ rm->seqno;
  60 }
  61
  62 static void htable_insert_connretrans(struct conn_retrans *cr)
  63 {
  64         struct retransmit_matchparam rm;
  65
  66         rm.conn_id = cr->rconn->target.out.conn_id;
  67         rm.seqno = cr->seqno;
  68         rm.nb = cr->rconn->target.out.nb;
  69
  70         htable_insert(&retransmits_conn, (char *) cr, rm_to_key(&rm));
  71 }
  72
  73 static int htable_delete_connretrans(struct conn_retrans *cr)
  74 {
  75         struct retransmit_matchparam rm;
  76
  77         rm.conn_id = cr->rconn->target.out.conn_id;
  78         rm.seqno = cr->seqno;
  79         rm.nb = cr->rconn->target.out.nb;
  80
  81         return htable_delete(&retransmits_conn, rm_to_key(&rm), &rm,
  82                         free_connretrans);
  83 }
  84
  85 /* static struct sk_buff * cor_dequeue(struct Qdisc *sch)
  86 {
  87         struct sk_buff *ret;
  88
  89         struct cor_sched_data *q = qdisc_priv(sch);
  90
  91         struct list_head *ln = q->conn_list.next;
  92         struct conn *best = 0;
  93
  94         __u64 currcost_limit = 0;
  95         __u64 currcost = 0;
  96
  97         spin_lock(&(q->lock));
  98
  99         if (!(skb_queue_empty(&(q->requeue_queue)))) {
 100                 ret = __skb_dequeue(&(q->requeue_queue));
 101                 goto out;
 102         }
 103
 104         while (&(q->conn_list) != ln) {
 105                 __u32 max1, max2, maxcost;
 106                 struct conn *curr = (struct conn *)
 107                                 (((char *) ln) - offsetof(struct conn,
 108                                                 target.out.queue_list));
 109
 110                 BUG_ON(TARGET_OUT != curr->targettype);
 111                 max1 = (256 * ((__u64)curr->credits)) /
 112                                 ((__u64)curr->bytes_queued + curr->avg_rate);
 113
 114                 max2 = (256 * ((__u64)curr->credits +
 115                                 curr->credit_sender - curr->credit_recp)) /
 116                                 ((__u64)curr->bytes_queued + 2*curr->avg_rate);
 117
 118                 maxcost = max((__u32) 0, min((max1), (max2)));
 119
 120                 if (maxcost > currcost_limit) {
 121                         currcost = currcost_limit;
 122                         currcost_limit = maxcost;
 123                         best = curr;
 124                 }
 125
 126                 ln = ln->next;
 127         }
 128
 129         best->credits -= currcost;
 130
 131         ret = __skb_dequeue(&(best->target.out.queue));
 132
 133         if (skb_queue_empty(&(best->target.out.queue))) {
 134                 list_del(&(best->target.out.queue_list));
 135                 best->target.out.qdisc_active = 0;
 136         }
 137
 138 out:
 139         spin_unlock(&(q->lock));
 140
 141         if (likely(0 != ret)) {
 142                 sch->qstats.backlog -= ret->len;
 143                 sch->q.qlen--;
 144         }
 145
 146         return ret;
 147 }
 148
 149 static int cor_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 150 {
 151         struct cor_sched_data *q = qdisc_priv(sch);
 152         struct conn *rconn;
 153
 154         rconn = skb_pstate(skb)->rconn;
 155
 156         BUG_ON(TARGET_OUT != rconn->targettype);
 157
 158         spin_lock(&(rconn->target.out.qdisc_lock));
 159
 160         __skb_queue_tail(&(rconn->target.out.queue), skb);
 161
 162         if (unlikely(0 == rconn->target.out.qdisc_active)) {
 163                 spin_lock(&(q->lock));
 164                 list_add(&(rconn->target.out.queue_list), &(q->conn_list));
 165                 rconn->target.out.qdisc_active = 1;
 166                 spin_unlock(&(q->lock));
 167         }
 168
 169         spin_unlock(&(rconn->target.out.qdisc_lock));
 170
 171         sch->bstats.bytes += skb->len;
 172         sch->bstats.packets++;
 173         sch->q.qlen++;
 174
 175         return NET_XMIT_SUCCESS;
 176 } */
 177
 178 struct sk_buff *create_packet(struct neighbor *nb, int size,
 179                 gfp_t alloc_flags, __u32 conn_id, __u32 seqno)
 180 {
 181         struct sk_buff *ret;
 182         char *dest;
 183
 184         ret = alloc_skb(size + 9 + LL_ALLOCATED_SPACE(nb->dev), alloc_flags);
 185         if (unlikely(0 == ret))
 186                 return 0;
 187
 188         ret->protocol = htons(ETH_P_COR);
 189         ret->dev = nb->dev;
 190
 191         skb_reserve(ret, LL_RESERVED_SPACE(nb->dev));
 192         if(unlikely(dev_hard_header(ret, nb->dev, ETH_P_COR, nb->mac,
 193                         nb->dev->dev_addr, ret->len) < 0))
 194                 return 0;
 195         skb_reset_network_header(ret);
 196
 197         dest = skb_put(ret, 9);
 198         BUG_ON(0 == dest);
 199
 200         dest[0] = PACKET_TYPE_DATA;
 201         dest += 1;
 202
 203         put_u32(dest, conn_id, 1);
 204         dest += 4;
 205         put_u32(dest, seqno, 1);
 206         dest += 4;
 207
 208         return ret;
 209 }
 210
 211 static void set_conn_retrans_timeout(struct conn_retrans *cr)
 212 {
 213         cr->timeout = jiffies + msecs_to_jiffies(300 + ((__u32) atomic_read(
 214                         &(cr->rconn->target.out.nb->latency)))/1000);
 215 }
 216
 217 static struct conn_retrans *readd_conn_retrans(struct conn_retrans *cr,
 218                 struct neighbor *nb, __u32 length, int *dontsend)
 219 {
 220         unsigned long iflags;
 221
 222         struct conn_retrans *ret = 0;
 223
 224         spin_lock_irqsave( &(nb->retrans_lock), iflags );
 225
 226         if (unlikely(cr->ackrcvd)) {
 227                 *dontsend = 1;
 228                 goto out;
 229         } else
 230                 *dontsend = 0;
 231
 232         if (unlikely(cr->length > length)) {
 233                 ret = kmem_cache_alloc(connretrans_slab, GFP_ATOMIC);
 234                 if (unlikely(ret == 0)) {
 235                         cr->timeout = jiffies + 1;
 236                         return 0;
 237                 }
 238
 239                 memset(ret, 0, sizeof (struct conn_retrans));
 240                 ret->rconn = cr->rconn;
 241                 kref_get(&(cr->rconn->ref));
 242                 ret->seqno = cr->seqno + length;
 243                 ret->length = cr->length - length;
 244                 kref_init(&(ret->ref));
 245         }
 246
 247         if (ret != 0) {
 248                 htable_insert_connretrans(ret);
 249                 list_add(&(ret->timeout_list), &(nb->retrans_list_conn));
 250                 list_add(&(ret->conn_list), &(cr->conn_list));
 251
 252                 cr->length = length;
 253         } else {
 254                 list_del(&(cr->timeout_list));
 255                 list_add_tail(&(cr->timeout_list), &(nb->retrans_list_conn));
 256                 set_conn_retrans_timeout(cr);
 257
 258                 BUG_ON(cr->length != length);
 259         }
 260
 261 out:
 262         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 263
 264         return ret;
 265 }
 266
 267 static void send_retrans(struct neighbor *nb, struct conn_retrans *cr)
 268 {
 269         int targetmss = mss(nb);
 270
 271         __u32 seqno = cr->seqno;
 272         __u32 length = cr->length;
 273
 274         int dontsend;
 275
 276         mutex_lock(&(cr->rconn->rcv_lock));
 277
 278         while (cr->length >= targetmss) {
 279                 struct sk_buff *skb;
 280                 char *dst;
 281                 skb = create_packet(nb, targetmss, GFP_KERNEL,
 282                                 cr->rconn->target.out.conn_id, seqno);
 283                 if (unlikely(skb == 0)) {
 284                         cr->timeout = jiffies + 1;
 285                         goto out;
 286                 }
 287
 288                 cr = readd_conn_retrans(cr, nb, targetmss, &dontsend);
 289                 if (unlikely(unlikely(dontsend) || unlikely(cr == 0 &&
 290                                 unlikely(cr->length > targetmss)))) {
 291                         kfree_skb(skb);
 292                         goto out;
 293                 }
 294
 295                 dst = skb_put(skb, targetmss);
 296
 297                 databuf_pullold(&(cr->rconn->buf), cr->seqno, dst, targetmss);
 298                 dev_queue_xmit(skb);
 299
 300                 seqno += targetmss;
 301                 length -= targetmss;
 302         }
 303
 304         if (cr->length > 0) {
 305                 struct control_msg_out *cm;
 306                 char *buf = kmalloc(cr->length, GFP_KERNEL);
 307
 308                 if (unlikely(buf == 0)) {
 309                         cr->timeout = jiffies + 1;
 310                         goto out;
 311                 }
 312
 313                 databuf_pullold(&(cr->rconn->buf), cr->seqno, buf, cr->length);
 314
 315                 cm = alloc_control_msg();
 316                 if (unlikely(cm == 0)) {
 317                         cr->timeout = jiffies + 1;
 318                         kfree(buf);
 319                         goto out;
 320                 }
 321
 322                 if (unlikely(readd_conn_retrans(cr, nb, cr->length, &dontsend)
 323                                 != 0))
 324                         BUG();
 325
 326                 if (likely(dontsend == 0))
 327                         send_conndata(cm, nb, cr->rconn->target.out.conn_id,
 328                                         cr->seqno, buf, buf, cr->length);
 329         }
 330
 331 out:
 332         mutex_unlock(&(cr->rconn->rcv_lock));
 333 }
 334
 335 void retransmit_conn_timerfunc(struct work_struct *work)
 336 {
 337         unsigned long iflags;
 338
 339         struct neighbor *nb = container_of(to_delayed_work(work),
 340                         struct neighbor, retrans_timer_conn);
 341
 342         struct conn_retrans *cr = 0;
 343
 344         int nbstate;
 345         int nbput = 0;
 346
 347         spin_lock_irqsave( &(nb->state_lock), iflags );
 348         nbstate = nb->state;
 349         spin_unlock_irqrestore( &(nb->state_lock), iflags );
 350
 351         while (1) {
 352                 spin_lock_irqsave( &(nb->retrans_lock), iflags );
 353
 354                 if (list_empty(&(nb->retrans_list_conn))) {
 355                         nb->retrans_timer_conn_running = 0;
 356                         nbput = 1;
 357                         break;
 358                 }
 359
 360                 cr = container_of(nb->retrans_list_conn.next,
 361                                 struct conn_retrans, timeout_list);
 362
 363                 BUG_ON(cr->rconn->targettype != TARGET_OUT);
 364
 365                 if (unlikely(unlikely(nbstate == NEIGHBOR_STATE_KILLED) ||
 366                                 unlikely(atomic_read(
 367                                 &(cr->rconn->isreset)) != 0))) {
 368                         htable_delete_connretrans(cr);
 369
 370                         list_del(&(cr->timeout_list));
 371                         list_del(&(cr->conn_list));
 372                         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 373
 374                         kref_put(&(cr->ref), free_connretrans);
 375                         continue;
 376                 }
 377
 378                 BUG_ON(nb != cr->rconn->target.out.nb);
 379
 380                 if (time_after(cr->timeout, jiffies)) {
 381                         mod_timer(&(nb->retrans_timer), cr->timeout);
 382                         break;
 383                 }
 384
 385                 kref_get(&(cr->ref));
 386                 spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 387                 send_retrans(nb, cr);
 388                 kref_put(&(cr->ref), free_connretrans);
 389         }
 390
 391         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 392
 393         if (nbput)
 394                 kref_put(&(nb->ref), neighbor_free);
 395 }
 396
 397 void conn_ack_rcvd(struct neighbor *nb, __u32 conn_id, __u32 seqno,
 398                 __u32 length)
 399 {
 400         unsigned long iflags;
 401         struct retransmit_matchparam rm;
 402         struct conn_retrans *cr;
 403
 404         #warning todo length
 405
 406         rm.conn_id = conn_id;
 407         rm.seqno = seqno;
 408         rm.nb = nb;
 409
 410         spin_lock_irqsave( &(nb->retrans_lock), iflags );
 411
 412         cr = (struct conn_retrans *) htable_get(&retransmits_conn,
 413                         rm_to_key(&rm), &rm);
 414
 415         if (unlikely(cr == 0)) {
 416                 printk(KERN_ERR "bogus/duplicate ack received");
 417                 goto out_err;
 418         }
 419
 420         BUG_ON(cr->rconn->targettype != TARGET_OUT);
 421
 422         if (unlikely(cr->rconn->target.out.nb != nb)) {
 423                 printk(KERN_ERR "invalid neigh when receiving ack");
 424                 goto out_err;
 425         }
 426
 427         if (unlikely(htable_delete_connretrans(cr)))
 428                 BUG();
 429
 430         list_del(&(cr->timeout_list));
 431         list_del(&(cr->conn_list));
 432         cr->ackrcvd = 1;
 433         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 434
 435         #warning todo databuf_ack
 436
 437         kref_put(&(cr->ref), free_connretrans);
 438
 439         return;
 440
 441 out_err:
 442         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 443 }
 444
 445 static int schedule_retransmit_conn(struct conn *rconn, __u32 seqno, __u32 len)
 446 {
 447         unsigned long iflags;
 448
 449         struct neighbor *nb = rconn->target.out.nb;
 450
 451         struct conn_retrans *cr;
 452         int first;
 453
 454         BUG_ON(rconn->targettype != TARGET_OUT);
 455
 456         cr = kmem_cache_alloc(connretrans_slab, GFP_KERNEL);
 457         if (unlikely(cr == 0))
 458                 return 1;
 459         memset(cr, 0, sizeof (struct conn_retrans));
 460         cr->rconn = rconn;
 461         kref_get(&(rconn->ref));
 462         cr->seqno = seqno;
 463         cr->length = len;
 464         kref_init(&(cr->ref));
 465         set_conn_retrans_timeout(cr);
 466
 467         spin_lock_irqsave( &(nb->retrans_lock), iflags );
 468
 469         htable_insert_connretrans(cr);
 470
 471         first = unlikely(list_empty(&(nb->retrans_list_conn)));
 472         list_add_tail(&(cr->timeout_list), &(nb->retrans_list_conn));
 473
 474         list_add_tail(&(cr->conn_list), &(rconn->target.out.retrans_list));
 475
 476         if (unlikely(unlikely(first) &&
 477                         unlikely(nb->retrans_timer_conn_running == 0))) {
 478                 __u32 delay = cr->timeout - jiffies;
 479                 schedule_delayed_work(&(nb->retrans_timer_conn), delay);
 480                 nb->retrans_timer_conn_running = 1;
 481                 kref_get(&(nb->ref));
 482         }
 483
 484         spin_unlock_irqrestore( &(nb->retrans_lock), iflags );
 485         return 0;
 486 }
 487
 488 void flush_out(struct conn *rconn)
 489 {
 490         int targetmss = mss(rconn->target.out.nb);
 491         __u32 seqno;
 492
 493         BUG_ON(rconn->targettype != TARGET_OUT);
 494
 495         if (unlikely(rconn->target.out.conn_id == 0))
 496                 return;
 497
 498         while (rconn->buf.read_remaining >= targetmss) {
 499                 struct sk_buff *skb;
 500                 char *dst;
 501                 seqno = rconn->target.out.seqno;
 502                 skb = create_packet(rconn->target.out.nb, targetmss, GFP_ATOMIC,
 503                                 rconn->target.out.conn_id, seqno);
 504                 if (unlikely(skb == 0))
 505                         goto oom;
 506
 507                 dst = skb_put(skb, targetmss);
 508
 509                 databuf_pull(&(rconn->buf), dst, targetmss);
 510
 511                 if (unlikely(schedule_retransmit_conn(rconn, seqno,
 512                                 targetmss))) {
 513                         kfree_skb(skb);
 514                         goto oom;
 515                 }
 516                 rconn->target.out.seqno += targetmss;
 517                 dev_queue_xmit(skb);
 518         }
 519
 520         if (rconn->buf.read_remaining > 0) {
 521                 struct control_msg_out *cm;
 522                 __u32 len = rconn->buf.read_remaining;
 523                 char *buf = kmalloc(len, GFP_KERNEL);
 524
 525                 if (unlikely(buf == 0))
 526                         goto oom;
 527
 528                 databuf_pull(&(rconn->buf), buf, len);
 529
 530                 cm = alloc_control_msg();
 531                 if (unlikely(cm == 0)) {
 532                         kfree(buf);
 533                         goto oom;
 534                 }
 535
 536                 seqno = rconn->target.out.seqno;
 537                 if (unlikely(schedule_retransmit_conn(rconn, seqno, len))) {
 538                         free_control_msg(cm);
 539                         goto oom;
 540                 }
 541
 542                 rconn->target.out.seqno += len;
 543
 544                 send_conndata(cm, rconn->target.out.nb,
 545                                 rconn->target.out.conn_id, seqno, buf, buf,
 546                                 len);
 547         }
 548
 549         wake_sender(rconn);
 550
 551         if (0) {
 552 oom:
 553                 #warning todo flush later
 554                 ;
 555         }
 556 }
 557
 558 static int matches_connretrans_connid_seqno(void *htentry, void *searcheditem)
 559 {
 560         struct conn_retrans *cr = (struct conn_retrans *) htentry;
 561         struct retransmit_matchparam *rm = (struct retransmit_matchparam *)
 562                         searcheditem;
 563         return rm->conn_id == cr->rconn->target.out.conn_id &&
 564                         rm->seqno == cr->seqno &&
 565                         rm->nb == cr->rconn->target.out.nb;
 566 }
 567
 568 int __init cor_snd_init(void)
 569 {
 570         connretrans_slab = kmem_cache_create("cor_connretrans",
 571                         sizeof(struct conn_retrans), 8, 0, 0);
 572         htable_init(&retransmits_conn, matches_connretrans_connid_seqno,
 573                         offsetof(struct conn_retrans, htab_entry),
 574                         offsetof(struct conn_retrans, ref));
 575
 576         return 0;
 577 }
 578
 579 MODULE_LICENSE("GPL");