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.5 (Berkeley) 10/04/90 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 #ifdef BSD4_3 361 fbuf->m_act = 0; /* probably not necessary */ 362 #else 363 { 364 register struct mbuf *m; 365 366 for (m = fbuf; m -> m_next; m = m -> m_next) 367 m -> m_act = (struct mbuf *) 0; 368 m -> m_act = (struct mbuf *) 1; 369 } 370 #endif 371 pk_input (fbuf, hdp->hd_xcp); 372 queued = TRUE; 373 hd_start (hdp); 374 } else { 375 /* 376 * Here if the remote station has transmitted more iframes then 377 * the number which have been acknowledged plus K. 378 */ 379 hdp->hd_invalid_ns++; 380 frame_reject (hdp, W, frame); 381 } 382 return (queued); 383 } 384 385 /* 386 * This routine is used to determine if a value (the middle parameter) 387 * is between two other values. The low value is the first parameter 388 * the high value is the last parameter. The routine checks the middle 389 * value to see if it is within the range of the first and last values. 390 * The reason we need this routine is the values are modulo some base 391 * hence a simple test for greater or less than is not sufficient. 392 */ 393 394 bool 395 range_check (rear, value, front) 396 int rear, 397 value, 398 front; 399 { 400 register bool result = FALSE; 401 402 if (front > rear) 403 result = (rear <= value) && (value <= front); 404 else 405 result = (rear <= value) || (value <= front); 406 407 return (result); 408 } 409 410 /* 411 * This routine handles all the frame reject conditions which can 412 * arise as a result of secondary processing. The frame reject 413 * condition Y (frame length error) are handled elsewhere. 414 */ 415 416 static 417 frame_reject (hdp, rejectcode, frame) 418 struct hdcb *hdp; 419 struct Hdlc_iframe *frame; 420 { 421 register struct Frmr_frame *frmr = &hd_frmr; 422 423 frmr -> frmr_control = ((struct Hdlc_frame *) frame) -> control; 424 425 frmr -> frmr_ns = frame -> ns; 426 frmr -> frmr_f1_0 = 0; 427 frmr -> frmr_nr = frame -> nr; 428 frmr -> frmr_f2_0 = 0; 429 430 frmr -> frmr_0000 = 0; 431 frmr -> frmr_w = frmr -> frmr_x = frmr -> frmr_y = 432 frmr -> frmr_z = 0; 433 switch (rejectcode) { 434 case Z: 435 frmr -> frmr_z = 1;/* invalid N(R). */ 436 break; 437 438 case Y: 439 frmr -> frmr_y = 1;/* iframe length error. */ 440 break; 441 442 case X: 443 frmr -> frmr_x = 1;/* invalid information field. */ 444 frmr -> frmr_w = 1; 445 break; 446 447 case W: 448 frmr -> frmr_w = 1;/* invalid N(S). */ 449 } 450 451 hd_writeinternal (hdp, FRMR, POLLOFF); 452 453 hdp->hd_state = WAIT_SABM; 454 SET_TIMER (hdp); 455 } 456 457 /* 458 * This procedure is invoked when ever we receive a supervisor 459 * frame such as RR, RNR and REJ. All processing for these 460 * frames is done here. 461 */ 462 463 process_sframe (hdp, frame, frametype) 464 register struct hdcb *hdp; 465 register struct Hdlc_sframe *frame; 466 int frametype; 467 { 468 register int nr = frame -> nr, pf = frame -> pf, pollbit = 0; 469 470 if (valid_nr (hdp, nr, pf) == TRUE) { 471 switch (frametype) { 472 case RR: 473 hdp->hd_condition &= ~REMOTE_RNR_CONDITION; 474 break; 475 476 case RNR: 477 hdp->hd_condition |= REMOTE_RNR_CONDITION; 478 hdp->hd_retxcnt = 0; 479 break; 480 481 case REJ: 482 hdp->hd_condition &= ~REMOTE_RNR_CONDITION; 483 rej_routine (hdp, nr); 484 } 485 486 if (pf == 1) { 487 hdp->hd_retxcnt = 0; 488 hdp->hd_condition &= ~TIMER_RECOVERY_CONDITION; 489 490 if (frametype == RR && hdp->hd_lastrxnr == hdp->hd_vs 491 && hdp->hd_timer == 0 && hdp->hd_txq.head == 0) 492 hd_writeinternal(hdp, RR, pf); 493 else 494 /* If any iframes have been queued because of the 495 timer condition, transmit then now. */ 496 if (hdp->hd_condition & REMOTE_RNR_CONDITION) { 497 /* Remote is busy or timer condition, so only 498 send one. */ 499 if (hdp->hd_vs != hdp->hd_retxqi) 500 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], pollbit); 501 } 502 else /* Flush the retransmit list first. */ 503 while (hdp->hd_vs != hdp->hd_retxqi) 504 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], POLLOFF); 505 } 506 507 hd_start (hdp); 508 } else 509 frame_reject (hdp, Z, (struct Hdlc_iframe *)frame); /* Invalid N(R). */ 510 } 511 512 /* 513 * This routine tests the validity of the N(R) which we have received. 514 * If it is ok, then all the iframes which it acknowledges (if any) 515 * will be freed. 516 */ 517 518 bool 519 valid_nr (hdp, nr, finalbit) 520 register struct hdcb *hdp; 521 register int finalbit; 522 { 523 /* Make sure it really does acknowledge something. */ 524 if (hdp->hd_lastrxnr == nr) 525 return (TRUE); 526 527 /* 528 * This section validates the frame's N(R) value. It's N(R) value 529 * must be in syncronization with our V(S) value and our "last 530 * received nr" variable. If it is correct then we are able to send 531 * more IFRAME's, else frame reject condition is entered. 532 */ 533 534 if (range_check (hdp->hd_lastrxnr, nr, hdp->hd_vs) == FALSE) { 535 if ((hdp->hd_condition & TIMER_RECOVERY_CONDITION) && 536 range_check (hdp->hd_vs, nr, hdp->hd_xx) == TRUE) 537 hdp->hd_vs = nr; 538 539 else { 540 hdp->hd_invalid_nr++; 541 return (FALSE); 542 } 543 } 544 545 /* 546 * If we get to here, we do have a valid frame but it might be out 547 * of sequence. However, we should still accept the receive state 548 * number N(R) since it has already passed our previous test and it 549 * does acknowledge frames which we are sending. 550 */ 551 552 KILL_TIMER (hdp); 553 free_iframes (hdp, &nr, finalbit);/* Free all acknowledged iframes */ 554 if (nr != hdp->hd_vs) 555 SET_TIMER (hdp); 556 557 return (TRUE); 558 } 559 560 /* 561 * This routine determines how many iframes need to be retransmitted. 562 * It then resets the Send State Variable V(S) to accomplish this. 563 */ 564 565 static 566 rej_routine (hdp, rejnr) 567 register struct hdcb *hdp; 568 register int rejnr; 569 { 570 register int anchor; 571 572 /* 573 * Flush the output queue. Any iframes queued for 574 * transmission will be out of sequence. 575 */ 576 577 hd_flush (hdp->hd_ifp); 578 579 /* 580 * Determine how many frames should be re-transmitted. In the case 581 * of a normal REJ this should be 1 to K. In the case of a timer 582 * recovery REJ (ie. a REJ with the Final Bit on) this could be 0. 583 */ 584 585 anchor = hdp->hd_vs; 586 if (hdp->hd_condition & TIMER_RECOVERY_CONDITION) 587 anchor = hdp->hd_xx; 588 589 anchor = (anchor - rejnr + 8) % MODULUS; 590 591 if (anchor > 0) { 592 593 /* There is at least one iframe to retransmit. */ 594 KILL_TIMER (hdp); 595 hdp->hd_vs = rejnr; 596 597 while (hdp->hd_vs != hdp->hd_retxqi) 598 hd_send_iframe (hdp, hdp->hd_retxq[hdp->hd_vs], POLLOFF); 599 600 } 601 hd_start (hdp); 602 } 603 604 /* 605 * This routine frees iframes from the retransmit queue. It is called 606 * when a previously written iframe is acknowledged. 607 */ 608 609 static 610 free_iframes (hdp, nr, finalbit) 611 register struct hdcb *hdp; 612 int *nr; 613 register int finalbit; 614 615 { 616 register int i, k; 617 618 /* 619 * We need to do the following because of a funny quirk in the 620 * protocol. This case occures when in Timer recovery condition 621 * we get a N(R) which acknowledges all the outstanding iframes 622 * but with the Final Bit off. In this case we need to save the last 623 * iframe for possible retransmission even though it has already been 624 * acknowledged! 625 */ 626 627 if ((hdp->hd_condition & TIMER_RECOVERY_CONDITION) && *nr == hdp->hd_xx && finalbit == 0) { 628 *nr = (*nr - 1 + 8) % MODULUS; 629 /* printf ("QUIRK\n"); */ 630 } 631 632 k = (*nr - hdp->hd_lastrxnr + 8) % MODULUS; 633 634 /* Loop here freeing all acknowledged iframes. */ 635 for (i = 0; i < k; ++i) { 636 m_freem (hdp->hd_retxq[hdp->hd_lastrxnr]); 637 hdp->hd_retxq[hdp->hd_lastrxnr] = 0; 638 hdp->hd_lastrxnr = (hdp->hd_lastrxnr + 1) % MODULUS; 639 } 640 641 } 642