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