1 /* 2 * Copyright (c) University of British Columbia, 1984 3 * Copyright (c) 1990 The Regents of the University of California. 4 * All rights reserved. 5 * 6 * This code is derived from software contributed to Berkeley by 7 * the Laboratory for Computation Vision and the Computer Science Department 8 * of the University of British Columbia. 9 * 10 * %sccs.include.redist.c% 11 * 12 * @(#)hd_input.c 7.6 (Berkeley) 01/09/91 13 */ 14 15 #include "param.h" 16 #include "systm.h" 17 #include "mbuf.h" 18 #include "domain.h" 19 #include "socket.h" 20 #include "protosw.h" 21 #include "errno.h" 22 #include "time.h" 23 #include "kernel.h" 24 25 #include "../net/if.h" 26 27 #include "hdlc.h" 28 #include "hd_var.h" 29 #include "x25.h" 30 31 /* 32 * HDLC INPUT INTERFACE 33 * 34 * This routine is called when the HDLC physical device has 35 * completed reading a frame. 36 */ 37 38 hdintr () 39 { 40 register struct mbuf *m; 41 register struct hdcb *hdp; 42 register struct ifnet *ifp; 43 register int s; 44 extern struct ifqueue pkintrq; 45 static struct ifnet *lastifp; 46 static struct hdcb *lasthdp; 47 48 for (;;) { 49 s = splimp (); 50 IF_DEQUEUE (&hdintrq, m); 51 splx (s); 52 if (m == 0) 53 break; 54 if (m->m_len < HDHEADERLN) { 55 printf ("hdintr: packet too short (len=%d)\n", 56 m->m_len); 57 m_freem (m); 58 continue; 59 } 60 if ((m->m_flags & M_PKTHDR) == 0) 61 panic("hdintr"); 62 ifp = m->m_pkthdr.rcvif; 63 64 /* 65 * look up the appropriate hdlc control block 66 */ 67 68 if (ifp == lastifp) 69 hdp = lasthdp; 70 else { 71 for (hdp = hdcbhead; hdp; hdp = hdp->hd_next) 72 if (hdp->hd_ifp == ifp) 73 break; 74 if (hdp == 0) { 75 printf ("hdintr: unknown interface %x\n", ifp); 76 m_freem (m); 77 continue; 78 } 79 lastifp = ifp; 80 lasthdp = hdp; 81 } 82 83 /* Process_rxframe returns FALSE if the frame was NOT queued 84 for the next higher layers. */ 85 if (process_rxframe (hdp, m) == FALSE) 86 m_freem (m); 87 } 88 if (pkintrq.ifq_len) 89 pkintr (); 90 } 91 92 process_rxframe (hdp, fbuf) 93 register struct hdcb *hdp; 94 register struct mbuf *fbuf; 95 { 96 register int queued = FALSE, frametype, pf; 97 register struct Hdlc_frame *frame; 98 99 frame = mtod (fbuf, struct Hdlc_frame *); 100 pf = ((struct Hdlc_iframe *) frame) -> pf; 101 102 hd_trace (hdp, RX, frame); 103 if (frame -> address != ADDRESS_A && frame -> address != ADDRESS_B) 104 return (queued); 105 106 switch ((frametype = hd_decode (hdp, frame)) + hdp->hd_state) { 107 case DM + DISC_SENT: 108 case UA + DISC_SENT: 109 /* 110 * Link now closed. Leave timer running 111 * so hd_timer() can periodically check the 112 * status of interface driver flag bit IFF_UP. 113 */ 114 hdp->hd_state = DISCONNECTED; 115 break; 116 117 case DM + INIT: 118 case UA + INIT: 119 /* 120 * This is a non-standard state change needed for DCEs 121 * that do dynamic link selection. We can't go into the 122 * usual "SEND DM" state because a DM is a SARM in LAP. 123 */ 124 hd_writeinternal (hdp, SABM, POLLOFF); 125 hdp->hd_state = SABM_SENT; 126 SET_TIMER (hdp); 127 break; 128 129 case SABM + DM_SENT: 130 case SABM + WAIT_SABM: 131 hd_writeinternal (hdp, UA, pf); 132 case UA + SABM_SENT: 133 case UA + WAIT_UA: 134 KILL_TIMER (hdp); 135 hd_initvars (hdp); 136 hdp->hd_state = ABM; 137 hd_message (hdp, "Link level operational"); 138 /* Notify the packet level - to send RESTART. */ 139 (void) pk_ctlinput (PRC_LINKUP, hdp->hd_xcp); 140 break; 141 142 case SABM + SABM_SENT: 143 /* Got a SABM collision. Acknowledge the remote's SABM 144 via UA but still wait for UA. */ 145 hd_writeinternal (hdp, UA, pf); 146 break; 147 148 case SABM + ABM: 149 /* Request to reset the link from the remote. */ 150 KILL_TIMER (hdp); 151 hd_message (hdp, "Link reset"); 152 #ifdef HDLCDEBUG 153 hd_dumptrace (hdp); 154 #endif 155 hd_flush (hdp->hd_ifp); 156 hd_writeinternal (hdp, UA, pf); 157 hd_initvars (hdp); 158 (void) pk_ctlinput (PRC_LINKRESET, hdp->hd_xcp); 159 hdp->hd_resets++; 160 break; 161 162 case SABM + WAIT_UA: 163 hd_writeinternal (hdp, UA, pf); 164 break; 165 166 case DM + ABM: 167 hd_message (hdp, "DM received: link down"); 168 #ifdef HDLCDEBUG 169 hd_dumptrace (hdp); 170 #endif 171 (void) pk_ctlinput (PRC_LINKDOWN, hdp->hd_xcp); 172 hd_flush (hdp->hd_ifp); 173 case DM + DM_SENT: 174 case DM + WAIT_SABM: 175 case DM + WAIT_UA: 176 hd_writeinternal (hdp, SABM, pf); 177 hdp->hd_state = SABM_SENT; 178 SET_TIMER (hdp); 179 break; 180 181 case DISC + INIT: 182 case DISC + DM_SENT: 183 case DISC + SABM_SENT: 184 /* Note: This is a non-standard state change. */ 185 hd_writeinternal (hdp, UA, pf); 186 hd_writeinternal (hdp, SABM, POLLOFF); 187 hdp->hd_state = SABM_SENT; 188 SET_TIMER (hdp); 189 break; 190 191 case DISC + WAIT_UA: 192 hd_writeinternal (hdp, DM, pf); 193 SET_TIMER (hdp); 194 hdp->hd_state = DM_SENT; 195 break; 196 197 case DISC + ABM: 198 hd_message (hdp, "DISC received: link down"); 199 (void) pk_ctlinput (PRC_LINKDOWN, hdp->hd_xcp); 200 case DISC + WAIT_SABM: 201 hd_writeinternal (hdp, UA, pf); 202 hdp->hd_state = DM_SENT; 203 SET_TIMER (hdp); 204 break; 205 206 case UA + ABM: 207 hd_message (hdp, "UA received: link down"); 208 (void) pk_ctlinput (PRC_LINKDOWN, hdp->hd_xcp); 209 case UA + WAIT_SABM: 210 hd_writeinternal (hdp, DM, pf); 211 hdp->hd_state = DM_SENT; 212 SET_TIMER (hdp); 213 break; 214 215 case FRMR + DM_SENT: 216 hd_writeinternal (hdp, SABM, pf); 217 hdp->hd_state = SABM_SENT; 218 SET_TIMER (hdp); 219 break; 220 221 case FRMR + WAIT_SABM: 222 hd_writeinternal (hdp, DM, pf); 223 hdp->hd_state = DM_SENT; 224 SET_TIMER (hdp); 225 break; 226 227 case FRMR + ABM: 228 hd_message (hdp, "FRMR received: link down"); 229 (void) pk_ctlinput (PRC_LINKDOWN, hdp->hd_xcp); 230 #ifdef HDLCDEBUG 231 hd_dumptrace (hdp); 232 #endif 233 hd_flush (hdp->hd_ifp); 234 hd_writeinternal (hdp, SABM, pf); 235 hdp->hd_state = WAIT_UA; 236 SET_TIMER (hdp); 237 break; 238 239 case RR + ABM: 240 case RNR + ABM: 241 case REJ + ABM: 242 process_sframe (hdp, (struct Hdlc_sframe *)frame, frametype); 243 break; 244 245 case IFRAME + ABM: 246 queued = process_iframe (hdp, fbuf, (struct Hdlc_iframe *)frame); 247 break; 248 249 case IFRAME + SABM_SENT: 250 case RR + SABM_SENT: 251 case RNR + SABM_SENT: 252 case REJ + SABM_SENT: 253 hd_writeinternal (hdp, DM, POLLON); 254 hdp->hd_state = DM_SENT; 255 SET_TIMER (hdp); 256 break; 257 258 case IFRAME + WAIT_SABM: 259 case RR + WAIT_SABM: 260 case RNR + WAIT_SABM: 261 case REJ + WAIT_SABM: 262 hd_writeinternal (hdp, FRMR, POLLOFF); 263 SET_TIMER (hdp); 264 break; 265 266 case ILLEGAL + SABM_SENT: 267 hdp->hd_unknown++; 268 hd_writeinternal (hdp, DM, POLLOFF); 269 hdp->hd_state = DM_SENT; 270 SET_TIMER (hdp); 271 break; 272 273 case ILLEGAL + ABM: 274 hd_message (hdp, "Unknown frame received: link down"); 275 (void) pk_ctlinput (PRC_LINKDOWN, hdp->hd_xcp); 276 case ILLEGAL + WAIT_SABM: 277 hdp->hd_unknown++; 278 #ifdef HDLCDEBUG 279 hd_dumptrace (hdp); 280 #endif 281 hd_writeinternal (hdp, FRMR, POLLOFF); 282 hdp->hd_state = WAIT_SABM; 283 SET_TIMER (hdp); 284 break; 285 } 286 287 return (queued); 288 } 289 290 process_iframe (hdp, fbuf, frame) 291 register struct hdcb *hdp; 292 struct mbuf *fbuf; 293 register struct Hdlc_iframe *frame; 294 { 295 register int nr = frame -> nr, 296 ns = frame -> ns, 297 pf = frame -> pf; 298 register int queued = FALSE; 299 300 /* 301 * Validate the iframe's N(R) value. It's N(R) value must be in 302 * sync with our V(S) value and our "last received nr". 303 */ 304 305 if (valid_nr (hdp, nr, FALSE) == FALSE) { 306 frame_reject (hdp, Z, frame); 307 return (queued); 308 } 309 310 311 /* 312 * This section tests the IFRAME for proper sequence. That is, it's 313 * sequence number N(S) MUST be equal to V(S). 314 */ 315 316 if (ns != hdp->hd_vr) { 317 hdp->hd_invalid_ns++; 318 if (pf || (hdp->hd_condition & REJ_CONDITION) == 0) { 319 hdp->hd_condition |= REJ_CONDITION; 320 /* 321 * Flush the transmit queue. This is ugly but we 322 * have no choice. A reject response must be 323 * immediately sent to the DCE. Failure to do so 324 * may result in another out of sequence iframe 325 * arriving (and thus sending another reject) 326 * before the first reject is transmitted. This 327 * will cause the DCE to receive two or more 328 * rejects back to back, which must never happen. 329 */ 330 hd_flush (hdp->hd_ifp); 331 hd_writeinternal (hdp, REJ, pf); 332 } 333 return (queued); 334 } 335 hdp->hd_condition &= ~REJ_CONDITION; 336 337 /* 338 * This section finally tests the IFRAME's sequence number against 339 * the window size (K) and the sequence number of the last frame 340 * we have acknowledged. If the IFRAME is completely correct then 341 * it is queued for the packet level. 342 */ 343 344 if (ns != (hdp->hd_lasttxnr + hdp->hd_xcp->xc_lwsize) % MODULUS) { 345 hdp->hd_vr = (hdp->hd_vr + 1) % MODULUS; 346 if (pf == 1) { 347 /* Must generate a RR or RNR with final bit on. */ 348 hd_writeinternal (hdp, RR, POLLON); 349 } else 350 /* 351 * Hopefully we can piggyback the RR, if not we will generate 352 * a RR when T3 timer expires. 353 */ 354 if (hdp -> hd_rrtimer == 0) 355 hdp->hd_rrtimer = hd_t3; 356 357 /* Forward iframe to packet level of X.25. */ 358 fbuf -> m_data += HDHEADERLN; 359 fbuf -> m_len -= HDHEADERLN; 360 fbuf -> m_pkthdr.len -= HDHEADERLN; 361 #ifdef BSD4_3 362 fbuf->m_act = 0; /* probably not necessary */ 363 #else 364 { 365 register struct mbuf *m; 366 367 for (m = fbuf; m -> m_next; m = m -> m_next) 368 m -> m_act = (struct mbuf *) 0; 369 m -> m_act = (struct mbuf *) 1; 370 } 371 #endif 372 pk_input (fbuf, hdp->hd_xcp); 373 queued = TRUE; 374 hd_start (hdp); 375 } else { 376 /* 377 * Here if the remote station has transmitted more iframes then 378 * the number which have been acknowledged plus K. 379 */ 380 hdp->hd_invalid_ns++; 381 frame_reject (hdp, W, frame); 382 } 383 return (queued); 384 } 385 386 /* 387 * This routine is used to determine if a value (the middle parameter) 388 * is between two other values. The low value is the first parameter 389 * the high value is the last parameter. The routine checks the middle 390 * value to see if it is within the range of the first and last values. 391 * The reason we need this routine is the values are modulo some base 392 * hence a simple test for greater or less than is not sufficient. 393 */ 394 395 bool 396 range_check (rear, value, front) 397 int rear, 398 value, 399 front; 400 { 401 register bool result = FALSE; 402 403 if (front > rear) 404 result = (rear <= value) && (value <= front); 405 else 406 result = (rear <= value) || (value <= front); 407 408 return (result); 409 } 410 411 /* 412 * This routine handles all the frame reject conditions which can 413 * arise as a result of secondary processing. The frame reject 414 * condition Y (frame length error) are handled elsewhere. 415 */ 416 417 static 418 frame_reject (hdp, rejectcode, frame) 419 struct hdcb *hdp; 420 struct Hdlc_iframe *frame; 421 { 422 register struct Frmr_frame *frmr = &hd_frmr; 423 424 frmr -> frmr_control = ((struct Hdlc_frame *) frame) -> control; 425 426 frmr -> frmr_ns = frame -> ns; 427 frmr -> frmr_f1_0 = 0; 428 frmr -> frmr_nr = frame -> nr; 429 frmr -> frmr_f2_0 = 0; 430 431 frmr -> frmr_0000 = 0; 432 frmr -> frmr_w = frmr -> frmr_x = frmr -> frmr_y = 433 frmr -> frmr_z = 0; 434 switch (rejectcode) { 435 case Z: 436 frmr -> frmr_z = 1;/* invalid N(R). */ 437 break; 438 439 case Y: 440 frmr -> frmr_y = 1;/* iframe length error. */ 441 break; 442 443 case X: 444 frmr -> frmr_x = 1;/* invalid information field. */ 445 frmr -> frmr_w = 1; 446 break; 447 448 case W: 449 frmr -> frmr_w = 1;/* invalid N(S). */ 450 } 451 452 hd_writeinternal (hdp, FRMR, POLLOFF); 453 454 hdp->hd_state = WAIT_SABM; 455 SET_TIMER (hdp); 456 } 457 458 /* 459 * This procedure is invoked when ever we receive a supervisor 460 * frame such as RR, RNR and REJ. All processing for these 461 * frames is done here. 462 */ 463 464 process_sframe (hdp, frame, frametype) 465 register struct hdcb *hdp; 466 register struct Hdlc_sframe *frame; 467 int frametype; 468 { 469 register int nr = frame -> nr, pf = frame -> pf, pollbit = 0; 470 471 if (valid_nr (hdp, nr, pf) == TRUE) { 472 switch (frametype) { 473 case RR: 474 hdp->hd_condition &= ~REMOTE_RNR_CONDITION; 475 break; 476 477 case RNR: 478 hdp->hd_condition |= REMOTE_RNR_CONDITION; 479 hdp->hd_retxcnt = 0; 480 break; 481 482 case REJ: 483 hdp->hd_condition &= ~REMOTE_RNR_CONDITION; 484 rej_routine (hdp, nr); 485 } 486 487 if (pf == 1) { 488 hdp->hd_retxcnt = 0; 489 hdp->hd_condition &= ~TIMER_RECOVERY_CONDITION; 490 491 if (frametype == RR && hdp->hd_lastrxnr == hdp->hd_vs 492 && hdp->hd_timer == 0 && hdp->hd_txq.head == 0) 493 hd_writeinternal(hdp, RR, pf); 494 else 495 /* If any iframes have been queued because of the 496 timer condition, transmit then now. */ 497 if (hdp->hd_condition & REMOTE_RNR_CONDITION) { 498 /* Remote is busy or timer condition, so only 499 send one. */ 500 if (hdp->hd_vs != hdp->hd_retxqi) 501 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], pollbit); 502 } 503 else /* Flush the retransmit list first. */ 504 while (hdp->hd_vs != hdp->hd_retxqi) 505 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], POLLOFF); 506 } 507 508 hd_start (hdp); 509 } else 510 frame_reject (hdp, Z, (struct Hdlc_iframe *)frame); /* Invalid N(R). */ 511 } 512 513 /* 514 * This routine tests the validity of the N(R) which we have received. 515 * If it is ok, then all the iframes which it acknowledges (if any) 516 * will be freed. 517 */ 518 519 bool 520 valid_nr (hdp, nr, finalbit) 521 register struct hdcb *hdp; 522 register int finalbit; 523 { 524 /* Make sure it really does acknowledge something. */ 525 if (hdp->hd_lastrxnr == nr) 526 return (TRUE); 527 528 /* 529 * This section validates the frame's N(R) value. It's N(R) value 530 * must be in syncronization with our V(S) value and our "last 531 * received nr" variable. If it is correct then we are able to send 532 * more IFRAME's, else frame reject condition is entered. 533 */ 534 535 if (range_check (hdp->hd_lastrxnr, nr, hdp->hd_vs) == FALSE) { 536 if ((hdp->hd_condition & TIMER_RECOVERY_CONDITION) && 537 range_check (hdp->hd_vs, nr, hdp->hd_xx) == TRUE) 538 hdp->hd_vs = nr; 539 540 else { 541 hdp->hd_invalid_nr++; 542 return (FALSE); 543 } 544 } 545 546 /* 547 * If we get to here, we do have a valid frame but it might be out 548 * of sequence. However, we should still accept the receive state 549 * number N(R) since it has already passed our previous test and it 550 * does acknowledge frames which we are sending. 551 */ 552 553 KILL_TIMER (hdp); 554 free_iframes (hdp, &nr, finalbit);/* Free all acknowledged iframes */ 555 if (nr != hdp->hd_vs) 556 SET_TIMER (hdp); 557 558 return (TRUE); 559 } 560 561 /* 562 * This routine determines how many iframes need to be retransmitted. 563 * It then resets the Send State Variable V(S) to accomplish this. 564 */ 565 566 static 567 rej_routine (hdp, rejnr) 568 register struct hdcb *hdp; 569 register int rejnr; 570 { 571 register int anchor; 572 573 /* 574 * Flush the output queue. Any iframes queued for 575 * transmission will be out of sequence. 576 */ 577 578 hd_flush (hdp->hd_ifp); 579 580 /* 581 * Determine how many frames should be re-transmitted. In the case 582 * of a normal REJ this should be 1 to K. In the case of a timer 583 * recovery REJ (ie. a REJ with the Final Bit on) this could be 0. 584 */ 585 586 anchor = hdp->hd_vs; 587 if (hdp->hd_condition & TIMER_RECOVERY_CONDITION) 588 anchor = hdp->hd_xx; 589 590 anchor = (anchor - rejnr + 8) % MODULUS; 591 592 if (anchor > 0) { 593 594 /* There is at least one iframe to retransmit. */ 595 KILL_TIMER (hdp); 596 hdp->hd_vs = rejnr; 597 598 while (hdp->hd_vs != hdp->hd_retxqi) 599 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], POLLOFF); 600 601 } 602 hd_start (hdp); 603 } 604 605 /* 606 * This routine frees iframes from the retransmit queue. It is called 607 * when a previously written iframe is acknowledged. 608 */ 609 610 static 611 free_iframes (hdp, nr, finalbit) 612 register struct hdcb *hdp; 613 int *nr; 614 register int finalbit; 615 616 { 617 register int i, k; 618 619 /* 620 * We need to do the following because of a funny quirk in the 621 * protocol. This case occures when in Timer recovery condition 622 * we get a N(R) which acknowledges all the outstanding iframes 623 * but with the Final Bit off. In this case we need to save the last 624 * iframe for possible retransmission even though it has already been 625 * acknowledged! 626 */ 627 628 if ((hdp->hd_condition & TIMER_RECOVERY_CONDITION) && *nr == hdp->hd_xx && finalbit == 0) { 629 *nr = (*nr - 1 + 8) % MODULUS; 630 /* printf ("QUIRK\n"); */ 631 } 632 633 k = (*nr - hdp->hd_lastrxnr + 8) % MODULUS; 634 635 /* Loop here freeing all acknowledged iframes. */ 636 for (i = 0; i < k; ++i) { 637 m_freem (hdp->hd_retxq[hdp->hd_lastrxnr]); 638 hdp->hd_retxq[hdp->hd_lastrxnr] = 0; 639 hdp->hd_lastrxnr = (hdp->hd_lastrxnr + 1) % MODULUS; 640 } 641 642 } 643