1 /* $OpenBSD: ppp-deflate.c,v 1.8 2007/09/15 16:43:51 henning Exp $ */ 2 /* $NetBSD: ppp-deflate.c,v 1.1 1996/03/15 02:28:09 paulus Exp $ */ 3 4 /* 5 * ppp_deflate.c - interface the zlib procedures for Deflate compression 6 * and decompression (as used by gzip) to the PPP code. 7 * This version is for use with mbufs on BSD-derived systems. 8 * 9 * Copyright (c) 1989-2002 Paul Mackerras. All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in 20 * the documentation and/or other materials provided with the 21 * distribution. 22 * 23 * 3. The name(s) of the authors of this software must not be used to 24 * endorse or promote products derived from this software without 25 * prior written permission. 26 * 27 * 4. Redistributions of any form whatsoever must retain the following 28 * acknowledgment: 29 * "This product includes software developed by Paul Mackerras 30 * <paulus@samba.org>". 31 * 32 * THE AUTHORS OF THIS SOFTWARE DISCLAIM ALL WARRANTIES WITH REGARD TO 33 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 34 * AND FITNESS, IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY 35 * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 36 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 37 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING 38 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 39 */ 40 41 #include <sys/param.h> 42 #include <sys/types.h> 43 #include <sys/systm.h> 44 #include <sys/mbuf.h> 45 #include <net/ppp_defs.h> 46 #include <net/zlib.h> 47 48 #define PACKETPTR struct mbuf * 49 #include <net/ppp-comp.h> 50 51 #if DO_DEFLATE 52 53 /* 54 * State for a Deflate (de)compressor. 55 */ 56 struct deflate_state { 57 int seqno; 58 int w_size; 59 int unit; 60 int hdrlen; 61 int mru; 62 int debug; 63 z_stream strm; 64 struct compstat stats; 65 }; 66 67 #define DEFLATE_OVHD 2 /* Deflate overhead/packet */ 68 69 static void *zalloc(void *, u_int items, u_int size); 70 static void zfree(void *, void *ptr, u_int nb); 71 static void *z_comp_alloc(u_char *options, int opt_len); 72 static void *z_decomp_alloc(u_char *options, int opt_len); 73 static void z_comp_free(void *state); 74 static void z_decomp_free(void *state); 75 static int z_comp_init(void *state, u_char *options, int opt_len, 76 int unit, int hdrlen, int debug); 77 static int z_decomp_init(void *state, u_char *options, int opt_len, 78 int unit, int hdrlen, int mru, int debug); 79 static int z_compress(void *state, struct mbuf **mret, 80 struct mbuf *mp, int slen, int maxolen); 81 static void z_incomp(void *state, struct mbuf *dmsg); 82 static int z_decompress(void *state, struct mbuf *cmp, 83 struct mbuf **dmpp); 84 static void z_comp_reset(void *state); 85 static void z_decomp_reset(void *state); 86 static void z_comp_stats(void *state, struct compstat *stats); 87 88 /* 89 * Procedures exported to if_ppp.c. 90 */ 91 struct compressor ppp_deflate = { 92 CI_DEFLATE, /* compress_proto */ 93 z_comp_alloc, /* comp_alloc */ 94 z_comp_free, /* comp_free */ 95 z_comp_init, /* comp_init */ 96 z_comp_reset, /* comp_reset */ 97 z_compress, /* compress */ 98 z_comp_stats, /* comp_stat */ 99 z_decomp_alloc, /* decomp_alloc */ 100 z_decomp_free, /* decomp_free */ 101 z_decomp_init, /* decomp_init */ 102 z_decomp_reset, /* decomp_reset */ 103 z_decompress, /* decompress */ 104 z_incomp, /* incomp */ 105 z_comp_stats, /* decomp_stat */ 106 }; 107 108 struct compressor ppp_deflate_draft = { 109 CI_DEFLATE_DRAFT, /* compress_proto */ 110 z_comp_alloc, /* comp_alloc */ 111 z_comp_free, /* comp_free */ 112 z_comp_init, /* comp_init */ 113 z_comp_reset, /* comp_reset */ 114 z_compress, /* compress */ 115 z_comp_stats, /* comp_stat */ 116 z_decomp_alloc, /* decomp_alloc */ 117 z_decomp_free, /* decomp_free */ 118 z_decomp_init, /* decomp_init */ 119 z_decomp_reset, /* decomp_reset */ 120 z_decompress, /* decompress */ 121 z_incomp, /* incomp */ 122 z_comp_stats, /* decomp_stat */ 123 }; 124 /* 125 * Space allocation and freeing routines for use by zlib routines. 126 */ 127 void * 128 zalloc(notused, items, size) 129 void *notused; 130 u_int items, size; 131 { 132 void *ptr; 133 134 ptr = malloc(items * size, M_DEVBUF, M_NOWAIT); 135 return ptr; 136 } 137 138 void 139 zfree(notused, ptr, nbytes) 140 void *notused; 141 void *ptr; 142 u_int nbytes; 143 { 144 free(ptr, M_DEVBUF); 145 } 146 147 /* 148 * Allocate space for a compressor. 149 */ 150 static void * 151 z_comp_alloc(options, opt_len) 152 u_char *options; 153 int opt_len; 154 { 155 struct deflate_state *state; 156 int w_size; 157 158 if (opt_len != CILEN_DEFLATE 159 || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT) 160 || options[1] != CILEN_DEFLATE 161 || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL 162 || options[3] != DEFLATE_CHK_SEQUENCE) 163 return NULL; 164 w_size = DEFLATE_SIZE(options[2]); 165 if (w_size < DEFLATE_MIN_SIZE || w_size > DEFLATE_MAX_SIZE) 166 return NULL; 167 168 state = malloc(sizeof(*state), M_DEVBUF, M_NOWAIT); 169 if (state == NULL) 170 return NULL; 171 172 state->strm.next_in = NULL; 173 state->strm.zalloc = zalloc; 174 state->strm.zfree = zfree; 175 if (deflateInit2(&state->strm, Z_DEFAULT_COMPRESSION, DEFLATE_METHOD_VAL, 176 -w_size, 8, Z_DEFAULT_STRATEGY, DEFLATE_OVHD+2) != Z_OK) { 177 free(state, M_DEVBUF); 178 return NULL; 179 } 180 181 state->w_size = w_size; 182 bzero(&state->stats, sizeof(state->stats)); 183 return (void *) state; 184 } 185 186 static void 187 z_comp_free(arg) 188 void *arg; 189 { 190 struct deflate_state *state = (struct deflate_state *) arg; 191 192 deflateEnd(&state->strm); 193 free(state, M_DEVBUF); 194 } 195 196 static int 197 z_comp_init(arg, options, opt_len, unit, hdrlen, debug) 198 void *arg; 199 u_char *options; 200 int opt_len, unit, hdrlen, debug; 201 { 202 struct deflate_state *state = (struct deflate_state *) arg; 203 204 if (opt_len < CILEN_DEFLATE 205 || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT) 206 || options[1] != CILEN_DEFLATE 207 || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL 208 || DEFLATE_SIZE(options[2]) != state->w_size 209 || options[3] != DEFLATE_CHK_SEQUENCE) 210 return 0; 211 212 state->seqno = 0; 213 state->unit = unit; 214 state->hdrlen = hdrlen; 215 state->debug = debug; 216 217 deflateReset(&state->strm); 218 219 return 1; 220 } 221 222 static void 223 z_comp_reset(arg) 224 void *arg; 225 { 226 struct deflate_state *state = (struct deflate_state *) arg; 227 228 state->seqno = 0; 229 deflateReset(&state->strm); 230 } 231 232 int 233 z_compress(arg, mret, mp, orig_len, maxolen) 234 void *arg; 235 struct mbuf **mret; /* compressed packet (out) */ 236 struct mbuf *mp; /* uncompressed packet (in) */ 237 int orig_len, maxolen; 238 { 239 struct deflate_state *state = (struct deflate_state *) arg; 240 u_char *rptr, *wptr; 241 int proto, olen, wspace, r, flush; 242 struct mbuf *m; 243 244 /* 245 * Check that the protocol is in the range we handle. 246 */ 247 rptr = mtod(mp, u_char *); 248 proto = PPP_PROTOCOL(rptr); 249 if (proto > 0x3fff || proto == 0xfd || proto == 0xfb) { 250 *mret = NULL; 251 return orig_len; 252 } 253 254 /* Allocate one mbuf initially. */ 255 if (maxolen > orig_len) 256 maxolen = orig_len; 257 MGET(m, M_DONTWAIT, MT_DATA); 258 *mret = m; 259 if (m != NULL) { 260 m->m_len = 0; 261 if (maxolen + state->hdrlen > MLEN) 262 MCLGET(m, M_DONTWAIT); 263 wspace = M_TRAILINGSPACE(m); 264 if (state->hdrlen + PPP_HDRLEN + 2 < wspace) { 265 m->m_data += state->hdrlen; 266 wspace -= state->hdrlen; 267 } 268 wptr = mtod(m, u_char *); 269 270 /* 271 * Copy over the PPP header and store the 2-byte sequence number. 272 */ 273 wptr[0] = PPP_ADDRESS(rptr); 274 wptr[1] = PPP_CONTROL(rptr); 275 wptr[2] = PPP_COMP >> 8; 276 wptr[3] = PPP_COMP; 277 wptr += PPP_HDRLEN; 278 wptr[0] = state->seqno >> 8; 279 wptr[1] = state->seqno; 280 wptr += 2; 281 state->strm.next_out = wptr; 282 state->strm.avail_out = wspace - (PPP_HDRLEN + 2); 283 } else { 284 state->strm.next_out = NULL; 285 state->strm.avail_out = 1000000; 286 wptr = NULL; 287 wspace = 0; 288 } 289 ++state->seqno; 290 291 rptr += (proto > 0xff)? 2: 3; /* skip 1st proto byte if 0 */ 292 state->strm.next_in = rptr; 293 state->strm.avail_in = mtod(mp, u_char *) + mp->m_len - rptr; 294 mp = mp->m_next; 295 flush = (mp == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH; 296 olen = 0; 297 for (;;) { 298 r = deflate(&state->strm, flush); 299 if (r != Z_OK) { 300 printf("z_compress: deflate returned %d (%s)\n", 301 r, (state->strm.msg? state->strm.msg: "")); 302 break; 303 } 304 if (flush != Z_NO_FLUSH && state->strm.avail_out != 0) 305 break; /* all done */ 306 if (state->strm.avail_in == 0 && mp != NULL) { 307 state->strm.next_in = mtod(mp, u_char *); 308 state->strm.avail_in = mp->m_len; 309 mp = mp->m_next; 310 if (mp == NULL) 311 flush = Z_PACKET_FLUSH; 312 } 313 if (state->strm.avail_out == 0) { 314 if (m != NULL) { 315 m->m_len = wspace; 316 olen += wspace; 317 MGET(m->m_next, M_DONTWAIT, MT_DATA); 318 m = m->m_next; 319 if (m != NULL) { 320 m->m_len = 0; 321 if (maxolen - olen > MLEN) 322 MCLGET(m, M_DONTWAIT); 323 state->strm.next_out = mtod(m, u_char *); 324 state->strm.avail_out = wspace = M_TRAILINGSPACE(m); 325 } 326 } 327 if (m == NULL) { 328 state->strm.next_out = NULL; 329 state->strm.avail_out = 1000000; 330 } 331 } 332 } 333 if (m != NULL) 334 olen += (m->m_len = wspace - state->strm.avail_out); 335 336 /* 337 * See if we managed to reduce the size of the packet. 338 * If the compressor just gave us a single zero byte, it means 339 * the packet was incompressible. 340 */ 341 if (m != NULL && olen < orig_len 342 && !(olen == PPP_HDRLEN + 3 && *wptr == 0)) { 343 state->stats.comp_bytes += olen; 344 state->stats.comp_packets++; 345 } else { 346 if (*mret != NULL) { 347 m_freem(*mret); 348 *mret = NULL; 349 } 350 state->stats.inc_bytes += orig_len; 351 state->stats.inc_packets++; 352 olen = orig_len; 353 } 354 state->stats.unc_bytes += orig_len; 355 state->stats.unc_packets++; 356 357 return olen; 358 } 359 360 static void 361 z_comp_stats(arg, stats) 362 void *arg; 363 struct compstat *stats; 364 { 365 struct deflate_state *state = (struct deflate_state *) arg; 366 u_int out; 367 368 *stats = state->stats; 369 stats->ratio = stats->unc_bytes; 370 out = stats->comp_bytes + stats->inc_bytes; 371 if (stats->ratio <= 0x7ffffff) 372 stats->ratio <<= 8; 373 else 374 out >>= 8; 375 if (out != 0) 376 stats->ratio /= out; 377 } 378 379 /* 380 * Allocate space for a decompressor. 381 */ 382 static void * 383 z_decomp_alloc(options, opt_len) 384 u_char *options; 385 int opt_len; 386 { 387 struct deflate_state *state; 388 int w_size; 389 390 if (opt_len != CILEN_DEFLATE 391 || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT) 392 || options[1] != CILEN_DEFLATE 393 || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL 394 || options[3] != DEFLATE_CHK_SEQUENCE) 395 return NULL; 396 w_size = DEFLATE_SIZE(options[2]); 397 if (w_size < DEFLATE_MIN_SIZE || w_size > DEFLATE_MAX_SIZE) 398 return NULL; 399 400 state = malloc(sizeof(*state), M_DEVBUF, M_NOWAIT); 401 if (state == NULL) 402 return NULL; 403 404 state->strm.next_out = NULL; 405 state->strm.zalloc = zalloc; 406 state->strm.zfree = zfree; 407 if (inflateInit2(&state->strm, -w_size) != Z_OK) { 408 free(state, M_DEVBUF); 409 return NULL; 410 } 411 412 state->w_size = w_size; 413 bzero(&state->stats, sizeof(state->stats)); 414 return (void *) state; 415 } 416 417 static void 418 z_decomp_free(arg) 419 void *arg; 420 { 421 struct deflate_state *state = (struct deflate_state *) arg; 422 423 inflateEnd(&state->strm); 424 free(state, M_DEVBUF); 425 } 426 427 static int 428 z_decomp_init(arg, options, opt_len, unit, hdrlen, mru, debug) 429 void *arg; 430 u_char *options; 431 int opt_len, unit, hdrlen, mru, debug; 432 { 433 struct deflate_state *state = (struct deflate_state *) arg; 434 435 if (opt_len < CILEN_DEFLATE 436 || (options[0] != CI_DEFLATE && options[0] != CI_DEFLATE_DRAFT) 437 || options[1] != CILEN_DEFLATE 438 || DEFLATE_METHOD(options[2]) != DEFLATE_METHOD_VAL 439 || DEFLATE_SIZE(options[2]) != state->w_size 440 || options[3] != DEFLATE_CHK_SEQUENCE) 441 return 0; 442 443 state->seqno = 0; 444 state->unit = unit; 445 state->hdrlen = hdrlen; 446 state->debug = debug; 447 state->mru = mru; 448 449 inflateReset(&state->strm); 450 451 return 1; 452 } 453 454 static void 455 z_decomp_reset(arg) 456 void *arg; 457 { 458 struct deflate_state *state = (struct deflate_state *) arg; 459 460 state->seqno = 0; 461 inflateReset(&state->strm); 462 } 463 464 /* 465 * Decompress a Deflate-compressed packet. 466 * 467 * Because of patent problems, we return DECOMP_ERROR for errors 468 * found by inspecting the input data and for system problems, but 469 * DECOMP_FATALERROR for any errors which could possibly be said to 470 * be being detected "after" decompression. For DECOMP_ERROR, 471 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be 472 * infringing a patent of Motorola's if we do, so we take CCP down 473 * instead. 474 * 475 * Given that the frame has the correct sequence number and a good FCS, 476 * errors such as invalid codes in the input most likely indicate a 477 * bug, so we return DECOMP_FATALERROR for them in order to turn off 478 * compression, even though they are detected by inspecting the input. 479 */ 480 int 481 z_decompress(arg, mi, mop) 482 void *arg; 483 struct mbuf *mi, **mop; 484 { 485 struct deflate_state *state = (struct deflate_state *) arg; 486 struct mbuf *mo, *mo_head; 487 u_char *rptr, *wptr; 488 int rlen, olen, ospace; 489 int seq, i, flush, r, decode_proto; 490 u_char hdr[PPP_HDRLEN + DEFLATE_OVHD]; 491 492 *mop = NULL; 493 rptr = mtod(mi, u_char *); 494 rlen = mi->m_len; 495 for (i = 0; i < PPP_HDRLEN + DEFLATE_OVHD; ++i) { 496 while (rlen <= 0) { 497 mi = mi->m_next; 498 if (mi == NULL) 499 return DECOMP_ERROR; 500 rptr = mtod(mi, u_char *); 501 rlen = mi->m_len; 502 } 503 hdr[i] = *rptr++; 504 --rlen; 505 } 506 507 /* Check the sequence number. */ 508 seq = (hdr[PPP_HDRLEN] << 8) + hdr[PPP_HDRLEN+1]; 509 if (seq != state->seqno) { 510 if (state->debug) 511 printf("z_decompress%d: bad seq # %d, expected %d\n", 512 state->unit, seq, state->seqno); 513 return DECOMP_ERROR; 514 } 515 ++state->seqno; 516 517 /* Allocate an output mbuf. */ 518 MGETHDR(mo, M_DONTWAIT, MT_DATA); 519 if (mo == NULL) 520 return DECOMP_ERROR; 521 mo_head = mo; 522 mo->m_len = 0; 523 mo->m_next = NULL; 524 MCLGET(mo, M_DONTWAIT); 525 ospace = M_TRAILINGSPACE(mo); 526 if (state->hdrlen + PPP_HDRLEN < ospace) { 527 mo->m_data += state->hdrlen; 528 ospace -= state->hdrlen; 529 } 530 531 /* 532 * Fill in the first part of the PPP header. The protocol field 533 * comes from the decompressed data. 534 */ 535 wptr = mtod(mo, u_char *); 536 wptr[0] = PPP_ADDRESS(hdr); 537 wptr[1] = PPP_CONTROL(hdr); 538 wptr[2] = 0; 539 540 /* 541 * Set up to call inflate. We set avail_out to 1 initially so we can 542 * look at the first byte of the output and decide whether we have 543 * a 1-byte or 2-byte protocol field. 544 */ 545 state->strm.next_in = rptr; 546 state->strm.avail_in = rlen; 547 mi = mi->m_next; 548 flush = (mi == NULL)? Z_PACKET_FLUSH: Z_NO_FLUSH; 549 rlen += PPP_HDRLEN + DEFLATE_OVHD; 550 state->strm.next_out = wptr + 3; 551 state->strm.avail_out = 1; 552 decode_proto = 1; 553 olen = PPP_HDRLEN; 554 555 /* 556 * Call inflate, supplying more input or output as needed. 557 */ 558 for (;;) { 559 r = inflate(&state->strm, flush); 560 if (r != Z_OK) { 561 #ifndef DEFLATE_DEBUG 562 if (state->debug) 563 #endif 564 printf("z_decompress%d: inflate returned %d (%s)\n", 565 state->unit, r, (state->strm.msg? state->strm.msg: "")); 566 m_freem(mo_head); 567 return DECOMP_FATALERROR; 568 } 569 if (flush != Z_NO_FLUSH && state->strm.avail_out != 0) 570 break; /* all done */ 571 if (state->strm.avail_in == 0 && mi != NULL) { 572 state->strm.next_in = mtod(mi, u_char *); 573 state->strm.avail_in = mi->m_len; 574 rlen += mi->m_len; 575 mi = mi->m_next; 576 if (mi == NULL) 577 flush = Z_PACKET_FLUSH; 578 } 579 if (state->strm.avail_out == 0) { 580 if (decode_proto) { 581 state->strm.avail_out = ospace - PPP_HDRLEN; 582 if ((wptr[3] & 1) == 0) { 583 /* 2-byte protocol field */ 584 wptr[2] = wptr[3]; 585 --state->strm.next_out; 586 ++state->strm.avail_out; 587 --olen; 588 } 589 decode_proto = 0; 590 } else { 591 mo->m_len = ospace; 592 olen += ospace; 593 MGET(mo->m_next, M_DONTWAIT, MT_DATA); 594 mo = mo->m_next; 595 if (mo == NULL) { 596 m_freem(mo_head); 597 return DECOMP_ERROR; 598 } 599 MCLGET(mo, M_DONTWAIT); 600 state->strm.next_out = mtod(mo, u_char *); 601 state->strm.avail_out = ospace = M_TRAILINGSPACE(mo); 602 } 603 } 604 } 605 if (decode_proto) { 606 m_freem(mo_head); 607 return DECOMP_ERROR; 608 } 609 olen += (mo->m_len = ospace - state->strm.avail_out); 610 #ifdef DEFLATE_DEBUG 611 if (olen > state->mru + PPP_HDRLEN) 612 printf("ppp_deflate%d: exceeded mru (%d > %d)\n", 613 state->unit, olen, state->mru + PPP_HDRLEN); 614 #endif 615 616 state->stats.unc_bytes += olen; 617 state->stats.unc_packets++; 618 state->stats.comp_bytes += rlen; 619 state->stats.comp_packets++; 620 621 *mop = mo_head; 622 return DECOMP_OK; 623 } 624 625 /* 626 * Incompressible data has arrived - add it to the history. 627 */ 628 static void 629 z_incomp(arg, mi) 630 void *arg; 631 struct mbuf *mi; 632 { 633 struct deflate_state *state = (struct deflate_state *) arg; 634 u_char *rptr; 635 int rlen, proto, r; 636 637 /* 638 * Check that the protocol is one we handle. 639 */ 640 rptr = mtod(mi, u_char *); 641 proto = PPP_PROTOCOL(rptr); 642 if (proto > 0x3fff || proto == 0xfd || proto == 0xfb) 643 return; 644 645 ++state->seqno; 646 647 /* 648 * Iterate through the mbufs, adding the characters in them 649 * to the decompressor's history. For the first mbuf, we start 650 * at the either the 1st or 2nd byte of the protocol field, 651 * depending on whether the protocol value is compressible. 652 */ 653 rlen = mi->m_len; 654 state->strm.next_in = rptr + 3; 655 state->strm.avail_in = rlen - 3; 656 if (proto > 0xff) { 657 --state->strm.next_in; 658 ++state->strm.avail_in; 659 } 660 for (;;) { 661 r = inflateIncomp(&state->strm); 662 if (r != Z_OK) { 663 /* gak! */ 664 #ifndef DEFLATE_DEBUG 665 if (state->debug) 666 #endif 667 printf("z_incomp%d: inflateIncomp returned %d (%s)\n", 668 state->unit, r, (state->strm.msg? state->strm.msg: "")); 669 return; 670 } 671 mi = mi->m_next; 672 if (mi == NULL) 673 break; 674 state->strm.next_in = mtod(mi, u_char *); 675 state->strm.avail_in = mi->m_len; 676 rlen += mi->m_len; 677 } 678 679 /* 680 * Update stats. 681 */ 682 state->stats.inc_bytes += rlen; 683 state->stats.inc_packets++; 684 state->stats.unc_bytes += rlen; 685 state->stats.unc_packets++; 686 } 687 688 #endif /* DO_DEFLATE */ 689