ia64/linux-2.6.18-xen.hg

view drivers/net/bsd_comp.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
line source
1 /*
2 * Update: The Berkeley copyright was changed, and the change
3 * is retroactive to all "true" BSD software (ie everything
4 * from UCB as opposed to other peoples code that just carried
5 * the same license). The new copyright doesn't clash with the
6 * GPL, so the module-only restriction has been removed..
7 */
9 /* Because this code is derived from the 4.3BSD compress source:
10 *
11 * Copyright (c) 1985, 1986 The Regents of the University of California.
12 * All rights reserved.
13 *
14 * This code is derived from software contributed to Berkeley by
15 * James A. Woods, derived from original work by Spencer Thomas
16 * and Joseph Orost.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. All advertising materials mentioning features or use of this software
27 * must display the following acknowledgement:
28 * This product includes software developed by the University of
29 * California, Berkeley and its contributors.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44 * SUCH DAMAGE.
45 */
47 /*
48 * This version is for use with contiguous buffers on Linux-derived systems.
49 *
50 * ==FILEVERSION 20000226==
51 *
52 * NOTE TO MAINTAINERS:
53 * If you modify this file at all, please set the number above to the
54 * date of the modification as YYMMDD (year month day).
55 * bsd_comp.c is shipped with a PPP distribution as well as with
56 * the kernel; if everyone increases the FILEVERSION number above,
57 * then scripts can do the right thing when deciding whether to
58 * install a new bsd_comp.c file. Don't change the format of that
59 * line otherwise, so the installation script can recognize it.
60 *
61 * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp
62 */
64 #include <linux/module.h>
65 #include <linux/init.h>
66 #include <linux/slab.h>
67 #include <linux/vmalloc.h>
68 #include <linux/string.h>
70 #include <linux/ppp_defs.h>
72 #undef PACKETPTR
73 #define PACKETPTR 1
74 #include <linux/ppp-comp.h>
75 #undef PACKETPTR
77 #include <asm/byteorder.h>
79 /*
80 * PPP "BSD compress" compression
81 * The differences between this compression and the classic BSD LZW
82 * source are obvious from the requirement that the classic code worked
83 * with files while this handles arbitrarily long streams that
84 * are broken into packets. They are:
85 *
86 * When the code size expands, a block of junk is not emitted by
87 * the compressor and not expected by the decompressor.
88 *
89 * New codes are not necessarily assigned every time an old
90 * code is output by the compressor. This is because a packet
91 * end forces a code to be emitted, but does not imply that a
92 * new sequence has been seen.
93 *
94 * The compression ratio is checked at the first end of a packet
95 * after the appropriate gap. Besides simplifying and speeding
96 * things up, this makes it more likely that the transmitter
97 * and receiver will agree when the dictionary is cleared when
98 * compression is not going well.
99 */
101 /*
102 * Macros to extract protocol version and number of bits
103 * from the third byte of the BSD Compress CCP configuration option.
104 */
106 #define BSD_VERSION(x) ((x) >> 5)
107 #define BSD_NBITS(x) ((x) & 0x1F)
109 #define BSD_CURRENT_VERSION 1
111 /*
112 * A dictionary for doing BSD compress.
113 */
115 struct bsd_dict {
116 union { /* hash value */
117 unsigned long fcode;
118 struct {
119 #if defined(__LITTLE_ENDIAN) /* Little endian order */
120 unsigned short prefix; /* preceding code */
121 unsigned char suffix; /* last character of new code */
122 unsigned char pad;
123 #elif defined(__BIG_ENDIAN) /* Big endian order */
124 unsigned char pad;
125 unsigned char suffix; /* last character of new code */
126 unsigned short prefix; /* preceding code */
127 #else
128 #error Endianness not defined...
129 #endif
130 } hs;
131 } f;
132 unsigned short codem1; /* output of hash table -1 */
133 unsigned short cptr; /* map code to hash table entry */
134 };
136 struct bsd_db {
137 int totlen; /* length of this structure */
138 unsigned int hsize; /* size of the hash table */
139 unsigned char hshift; /* used in hash function */
140 unsigned char n_bits; /* current bits/code */
141 unsigned char maxbits; /* maximum bits/code */
142 unsigned char debug; /* non-zero if debug desired */
143 unsigned char unit; /* ppp unit number */
144 unsigned short seqno; /* sequence # of next packet */
145 unsigned int mru; /* size of receive (decompress) bufr */
146 unsigned int maxmaxcode; /* largest valid code */
147 unsigned int max_ent; /* largest code in use */
148 unsigned int in_count; /* uncompressed bytes, aged */
149 unsigned int bytes_out; /* compressed bytes, aged */
150 unsigned int ratio; /* recent compression ratio */
151 unsigned int checkpoint; /* when to next check the ratio */
152 unsigned int clear_count; /* times dictionary cleared */
153 unsigned int incomp_count; /* incompressible packets */
154 unsigned int incomp_bytes; /* incompressible bytes */
155 unsigned int uncomp_count; /* uncompressed packets */
156 unsigned int uncomp_bytes; /* uncompressed bytes */
157 unsigned int comp_count; /* compressed packets */
158 unsigned int comp_bytes; /* compressed bytes */
159 unsigned short *lens; /* array of lengths of codes */
160 struct bsd_dict *dict; /* dictionary */
161 };
163 #define BSD_OVHD 2 /* BSD compress overhead/packet */
164 #define MIN_BSD_BITS 9
165 #define BSD_INIT_BITS MIN_BSD_BITS
166 #define MAX_BSD_BITS 15
168 static void bsd_free (void *state);
169 static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);
170 static void *bsd_comp_alloc (unsigned char *options, int opt_len);
171 static void *bsd_decomp_alloc (unsigned char *options, int opt_len);
173 static int bsd_init (void *db, unsigned char *options,
174 int opt_len, int unit, int debug, int decomp);
175 static int bsd_comp_init (void *state, unsigned char *options,
176 int opt_len, int unit, int opthdr, int debug);
177 static int bsd_decomp_init (void *state, unsigned char *options,
178 int opt_len, int unit, int opthdr, int mru,
179 int debug);
181 static void bsd_reset (void *state);
182 static void bsd_comp_stats (void *state, struct compstat *stats);
184 static int bsd_compress (void *state, unsigned char *rptr,
185 unsigned char *obuf, int isize, int osize);
186 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);
188 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
189 unsigned char *obuf, int osize);
191 /* These are in ppp_generic.c */
192 extern int ppp_register_compressor (struct compressor *cp);
193 extern void ppp_unregister_compressor (struct compressor *cp);
195 /*
196 * the next two codes should not be changed lightly, as they must not
197 * lie within the contiguous general code space.
198 */
199 #define CLEAR 256 /* table clear output code */
200 #define FIRST 257 /* first free entry */
201 #define LAST 255
203 #define MAXCODE(b) ((1 << (b)) - 1)
204 #define BADCODEM1 MAXCODE(MAX_BSD_BITS);
206 #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \
207 ^ (unsigned long)(prefix))
208 #define BSD_KEY(prefix,suffix) ((((unsigned long)(suffix)) << 16) \
209 + (unsigned long)(prefix))
211 #define CHECK_GAP 10000 /* Ratio check interval */
213 #define RATIO_SCALE_LOG 8
214 #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
215 #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
217 /*
218 * clear the dictionary
219 */
221 static void
222 bsd_clear(struct bsd_db *db)
223 {
224 db->clear_count++;
225 db->max_ent = FIRST-1;
226 db->n_bits = BSD_INIT_BITS;
227 db->bytes_out = 0;
228 db->in_count = 0;
229 db->ratio = 0;
230 db->checkpoint = CHECK_GAP;
231 }
233 /*
234 * If the dictionary is full, then see if it is time to reset it.
235 *
236 * Compute the compression ratio using fixed-point arithmetic
237 * with 8 fractional bits.
238 *
239 * Since we have an infinite stream instead of a single file,
240 * watch only the local compression ratio.
241 *
242 * Since both peers must reset the dictionary at the same time even in
243 * the absence of CLEAR codes (while packets are incompressible), they
244 * must compute the same ratio.
245 */
247 static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */
248 {
249 unsigned int new_ratio;
251 if (db->in_count >= db->checkpoint)
252 {
253 /* age the ratio by limiting the size of the counts */
254 if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
255 {
256 db->in_count -= (db->in_count >> 2);
257 db->bytes_out -= (db->bytes_out >> 2);
258 }
260 db->checkpoint = db->in_count + CHECK_GAP;
262 if (db->max_ent >= db->maxmaxcode)
263 {
264 /* Reset the dictionary only if the ratio is worse,
265 * or if it looks as if it has been poisoned
266 * by incompressible data.
267 *
268 * This does not overflow, because
269 * db->in_count <= RATIO_MAX.
270 */
272 new_ratio = db->in_count << RATIO_SCALE_LOG;
273 if (db->bytes_out != 0)
274 {
275 new_ratio /= db->bytes_out;
276 }
278 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
279 {
280 bsd_clear (db);
281 return 1;
282 }
283 db->ratio = new_ratio;
284 }
285 }
286 return 0;
287 }
289 /*
290 * Return statistics.
291 */
293 static void bsd_comp_stats (void *state, struct compstat *stats)
294 {
295 struct bsd_db *db = (struct bsd_db *) state;
297 stats->unc_bytes = db->uncomp_bytes;
298 stats->unc_packets = db->uncomp_count;
299 stats->comp_bytes = db->comp_bytes;
300 stats->comp_packets = db->comp_count;
301 stats->inc_bytes = db->incomp_bytes;
302 stats->inc_packets = db->incomp_count;
303 stats->in_count = db->in_count;
304 stats->bytes_out = db->bytes_out;
305 }
307 /*
308 * Reset state, as on a CCP ResetReq.
309 */
311 static void bsd_reset (void *state)
312 {
313 struct bsd_db *db = (struct bsd_db *) state;
315 bsd_clear(db);
317 db->seqno = 0;
318 db->clear_count = 0;
319 }
321 /*
322 * Release the compression structure
323 */
325 static void bsd_free (void *state)
326 {
327 struct bsd_db *db = state;
329 if (!db)
330 return;
332 /*
333 * Release the dictionary
334 */
335 vfree(db->dict);
336 db->dict = NULL;
337 /*
338 * Release the string buffer
339 */
340 vfree(db->lens);
341 db->lens = NULL;
342 /*
343 * Finally release the structure itself.
344 */
345 kfree(db);
346 }
348 /*
349 * Allocate space for a (de) compressor.
350 */
352 static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
353 {
354 int bits;
355 unsigned int hsize, hshift, maxmaxcode;
356 struct bsd_db *db;
358 if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
359 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
360 {
361 return NULL;
362 }
364 bits = BSD_NBITS(options[2]);
366 switch (bits)
367 {
368 case 9: /* needs 82152 for both directions */
369 case 10: /* needs 84144 */
370 case 11: /* needs 88240 */
371 case 12: /* needs 96432 */
372 hsize = 5003;
373 hshift = 4;
374 break;
375 case 13: /* needs 176784 */
376 hsize = 9001;
377 hshift = 5;
378 break;
379 case 14: /* needs 353744 */
380 hsize = 18013;
381 hshift = 6;
382 break;
383 case 15: /* needs 691440 */
384 hsize = 35023;
385 hshift = 7;
386 break;
387 case 16: /* needs 1366160--far too much, */
388 /* hsize = 69001; */ /* and 69001 is too big for cptr */
389 /* hshift = 8; */ /* in struct bsd_db */
390 /* break; */
391 default:
392 return NULL;
393 }
394 /*
395 * Allocate the main control structure for this instance.
396 */
397 maxmaxcode = MAXCODE(bits);
398 db = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),
399 GFP_KERNEL);
400 if (!db)
401 {
402 return NULL;
403 }
405 memset (db, 0, sizeof(struct bsd_db));
406 /*
407 * Allocate space for the dictionary. This may be more than one page in
408 * length.
409 */
410 db->dict = (struct bsd_dict *) vmalloc (hsize *
411 sizeof (struct bsd_dict));
412 if (!db->dict)
413 {
414 bsd_free (db);
415 return NULL;
416 }
418 /*
419 * If this is the compression buffer then there is no length data.
420 */
421 if (!decomp)
422 {
423 db->lens = NULL;
424 }
425 /*
426 * For decompression, the length information is needed as well.
427 */
428 else
429 {
430 db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
431 sizeof (db->lens[0]));
432 if (!db->lens)
433 {
434 bsd_free (db);
435 return (NULL);
436 }
437 }
438 /*
439 * Initialize the data information for the compression code
440 */
441 db->totlen = sizeof (struct bsd_db) +
442 (sizeof (struct bsd_dict) * hsize);
444 db->hsize = hsize;
445 db->hshift = hshift;
446 db->maxmaxcode = maxmaxcode;
447 db->maxbits = bits;
449 return (void *) db;
450 }
452 static void *bsd_comp_alloc (unsigned char *options, int opt_len)
453 {
454 return bsd_alloc (options, opt_len, 0);
455 }
457 static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
458 {
459 return bsd_alloc (options, opt_len, 1);
460 }
462 /*
463 * Initialize the database.
464 */
466 static int bsd_init (void *state, unsigned char *options,
467 int opt_len, int unit, int debug, int decomp)
468 {
469 struct bsd_db *db = state;
470 int indx;
472 if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
473 || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
474 || (BSD_NBITS(options[2]) != db->maxbits)
475 || (decomp && db->lens == NULL))
476 {
477 return 0;
478 }
480 if (decomp)
481 {
482 indx = LAST;
483 do
484 {
485 db->lens[indx] = 1;
486 }
487 while (indx-- > 0);
488 }
490 indx = db->hsize;
491 while (indx-- != 0)
492 {
493 db->dict[indx].codem1 = BADCODEM1;
494 db->dict[indx].cptr = 0;
495 }
497 db->unit = unit;
498 db->mru = 0;
499 #ifndef DEBUG
500 if (debug)
501 #endif
502 db->debug = 1;
504 bsd_reset(db);
506 return 1;
507 }
509 static int bsd_comp_init (void *state, unsigned char *options,
510 int opt_len, int unit, int opthdr, int debug)
511 {
512 return bsd_init (state, options, opt_len, unit, debug, 0);
513 }
515 static int bsd_decomp_init (void *state, unsigned char *options,
516 int opt_len, int unit, int opthdr, int mru,
517 int debug)
518 {
519 return bsd_init (state, options, opt_len, unit, debug, 1);
520 }
522 /*
523 * Obtain pointers to the various structures in the compression tables
524 */
526 #define dict_ptrx(p,idx) &(p->dict[idx])
527 #define lens_ptrx(p,idx) &(p->lens[idx])
529 #ifdef DEBUG
530 static unsigned short *lens_ptr(struct bsd_db *db, int idx)
531 {
532 if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
533 {
534 printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
535 idx = 0;
536 }
537 return lens_ptrx (db, idx);
538 }
540 static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
541 {
542 if ((unsigned int) idx >= (unsigned int) db->hsize)
543 {
544 printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
545 idx = 0;
546 }
547 return dict_ptrx (db, idx);
548 }
550 #else
551 #define lens_ptr(db,idx) lens_ptrx(db,idx)
552 #define dict_ptr(db,idx) dict_ptrx(db,idx)
553 #endif
555 /*
556 * compress a packet
557 *
558 * The result of this function is the size of the compressed
559 * packet. A zero is returned if the packet was not compressed
560 * for some reason, such as the size being larger than uncompressed.
561 *
562 * One change from the BSD compress command is that when the
563 * code size expands, we do not output a bunch of padding.
564 */
566 static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
567 int isize, int osize)
568 {
569 struct bsd_db *db;
570 int hshift;
571 unsigned int max_ent;
572 unsigned int n_bits;
573 unsigned int bitno;
574 unsigned long accm;
575 int ent;
576 unsigned long fcode;
577 struct bsd_dict *dictp;
578 unsigned char c;
579 int hval;
580 int disp;
581 int ilen;
582 int mxcode;
583 unsigned char *wptr;
584 int olen;
586 #define PUTBYTE(v) \
587 { \
588 ++olen; \
589 if (wptr) \
590 { \
591 *wptr++ = (unsigned char) (v); \
592 if (olen >= osize) \
593 { \
594 wptr = NULL; \
595 } \
596 } \
597 }
599 #define OUTPUT(ent) \
600 { \
601 bitno -= n_bits; \
602 accm |= ((ent) << bitno); \
603 do \
604 { \
605 PUTBYTE(accm >> 24); \
606 accm <<= 8; \
607 bitno += 8; \
608 } \
609 while (bitno <= 24); \
610 }
612 /*
613 * If the protocol is not in the range we're interested in,
614 * just return without compressing the packet. If it is,
615 * the protocol becomes the first byte to compress.
616 */
618 ent = PPP_PROTOCOL(rptr);
619 if (ent < 0x21 || ent > 0xf9)
620 {
621 return 0;
622 }
624 db = (struct bsd_db *) state;
625 hshift = db->hshift;
626 max_ent = db->max_ent;
627 n_bits = db->n_bits;
628 bitno = 32;
629 accm = 0;
630 mxcode = MAXCODE (n_bits);
632 /* Initialize the output pointers */
633 wptr = obuf;
634 olen = PPP_HDRLEN + BSD_OVHD;
636 if (osize > isize)
637 {
638 osize = isize;
639 }
641 /* This is the PPP header information */
642 if (wptr)
643 {
644 *wptr++ = PPP_ADDRESS(rptr);
645 *wptr++ = PPP_CONTROL(rptr);
646 *wptr++ = 0;
647 *wptr++ = PPP_COMP;
648 *wptr++ = db->seqno >> 8;
649 *wptr++ = db->seqno;
650 }
652 /* Skip the input header */
653 rptr += PPP_HDRLEN;
654 isize -= PPP_HDRLEN;
655 ilen = ++isize; /* Low byte of protocol is counted as input */
657 while (--ilen > 0)
658 {
659 c = *rptr++;
660 fcode = BSD_KEY (ent, c);
661 hval = BSD_HASH (ent, c, hshift);
662 dictp = dict_ptr (db, hval);
664 /* Validate and then check the entry. */
665 if (dictp->codem1 >= max_ent)
666 {
667 goto nomatch;
668 }
670 if (dictp->f.fcode == fcode)
671 {
672 ent = dictp->codem1 + 1;
673 continue; /* found (prefix,suffix) */
674 }
676 /* continue probing until a match or invalid entry */
677 disp = (hval == 0) ? 1 : hval;
679 do
680 {
681 hval += disp;
682 if (hval >= db->hsize)
683 {
684 hval -= db->hsize;
685 }
686 dictp = dict_ptr (db, hval);
687 if (dictp->codem1 >= max_ent)
688 {
689 goto nomatch;
690 }
691 }
692 while (dictp->f.fcode != fcode);
694 ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
695 continue;
697 nomatch:
698 OUTPUT(ent); /* output the prefix */
700 /* code -> hashtable */
701 if (max_ent < db->maxmaxcode)
702 {
703 struct bsd_dict *dictp2;
704 struct bsd_dict *dictp3;
705 int indx;
707 /* expand code size if needed */
708 if (max_ent >= mxcode)
709 {
710 db->n_bits = ++n_bits;
711 mxcode = MAXCODE (n_bits);
712 }
714 /* Invalidate old hash table entry using
715 * this code, and then take it over.
716 */
718 dictp2 = dict_ptr (db, max_ent + 1);
719 indx = dictp2->cptr;
720 dictp3 = dict_ptr (db, indx);
722 if (dictp3->codem1 == max_ent)
723 {
724 dictp3->codem1 = BADCODEM1;
725 }
727 dictp2->cptr = hval;
728 dictp->codem1 = max_ent;
729 dictp->f.fcode = fcode;
730 db->max_ent = ++max_ent;
732 if (db->lens)
733 {
734 unsigned short *len1 = lens_ptr (db, max_ent);
735 unsigned short *len2 = lens_ptr (db, ent);
736 *len1 = *len2 + 1;
737 }
738 }
739 ent = c;
740 }
742 OUTPUT(ent); /* output the last code */
744 db->bytes_out += olen - PPP_HDRLEN - BSD_OVHD;
745 db->uncomp_bytes += isize;
746 db->in_count += isize;
747 ++db->uncomp_count;
748 ++db->seqno;
750 if (bitno < 32)
751 {
752 ++db->bytes_out; /* must be set before calling bsd_check */
753 }
755 /*
756 * Generate the clear command if needed
757 */
759 if (bsd_check(db))
760 {
761 OUTPUT (CLEAR);
762 }
764 /*
765 * Pad dribble bits of last code with ones.
766 * Do not emit a completely useless byte of ones.
767 */
769 if (bitno != 32)
770 {
771 PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
772 }
774 /*
775 * Increase code size if we would have without the packet
776 * boundary because the decompressor will do so.
777 */
779 if (max_ent >= mxcode && max_ent < db->maxmaxcode)
780 {
781 db->n_bits++;
782 }
784 /* If output length is too large then this is an incomplete frame. */
785 if (wptr == NULL)
786 {
787 ++db->incomp_count;
788 db->incomp_bytes += isize;
789 olen = 0;
790 }
791 else /* Count the number of compressed frames */
792 {
793 ++db->comp_count;
794 db->comp_bytes += olen;
795 }
797 /* Return the resulting output length */
798 return olen;
799 #undef OUTPUT
800 #undef PUTBYTE
801 }
803 /*
804 * Update the "BSD Compress" dictionary on the receiver for
805 * incompressible data by pretending to compress the incoming data.
806 */
808 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
809 {
810 (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
811 }
813 /*
814 * Decompress "BSD Compress".
815 *
816 * Because of patent problems, we return DECOMP_ERROR for errors
817 * found by inspecting the input data and for system problems, but
818 * DECOMP_FATALERROR for any errors which could possibly be said to
819 * be being detected "after" decompression. For DECOMP_ERROR,
820 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
821 * infringing a patent of Motorola's if we do, so we take CCP down
822 * instead.
823 *
824 * Given that the frame has the correct sequence number and a good FCS,
825 * errors such as invalid codes in the input most likely indicate a
826 * bug, so we return DECOMP_FATALERROR for them in order to turn off
827 * compression, even though they are detected by inspecting the input.
828 */
830 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
831 unsigned char *obuf, int osize)
832 {
833 struct bsd_db *db;
834 unsigned int max_ent;
835 unsigned long accm;
836 unsigned int bitno; /* 1st valid bit in accm */
837 unsigned int n_bits;
838 unsigned int tgtbitno; /* bitno when we have a code */
839 struct bsd_dict *dictp;
840 int explen;
841 int seq;
842 unsigned int incode;
843 unsigned int oldcode;
844 unsigned int finchar;
845 unsigned char *p;
846 unsigned char *wptr;
847 int adrs;
848 int ctrl;
849 int ilen;
850 int codelen;
851 int extra;
853 db = (struct bsd_db *) state;
854 max_ent = db->max_ent;
855 accm = 0;
856 bitno = 32; /* 1st valid bit in accm */
857 n_bits = db->n_bits;
858 tgtbitno = 32 - n_bits; /* bitno when we have a code */
860 /*
861 * Save the address/control from the PPP header
862 * and then get the sequence number.
863 */
865 adrs = PPP_ADDRESS (ibuf);
866 ctrl = PPP_CONTROL (ibuf);
868 seq = (ibuf[4] << 8) + ibuf[5];
870 ibuf += (PPP_HDRLEN + 2);
871 ilen = isize - (PPP_HDRLEN + 2);
873 /*
874 * Check the sequence number and give up if it differs from
875 * the value we're expecting.
876 */
878 if (seq != db->seqno)
879 {
880 if (db->debug)
881 {
882 printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
883 db->unit, seq, db->seqno - 1);
884 }
885 return DECOMP_ERROR;
886 }
888 ++db->seqno;
889 db->bytes_out += ilen;
891 /*
892 * Fill in the ppp header, but not the last byte of the protocol
893 * (that comes from the decompressed data).
894 */
896 wptr = obuf;
897 *wptr++ = adrs;
898 *wptr++ = ctrl;
899 *wptr++ = 0;
901 oldcode = CLEAR;
902 explen = 3;
904 /*
905 * Keep the checkpoint correctly so that incompressible packets
906 * clear the dictionary at the proper times.
907 */
909 for (;;)
910 {
911 if (ilen-- <= 0)
912 {
913 db->in_count += (explen - 3); /* don't count the header */
914 break;
915 }
917 /*
918 * Accumulate bytes until we have a complete code.
919 * Then get the next code, relying on the 32-bit,
920 * unsigned accm to mask the result.
921 */
923 bitno -= 8;
924 accm |= *ibuf++ << bitno;
925 if (tgtbitno < bitno)
926 {
927 continue;
928 }
930 incode = accm >> tgtbitno;
931 accm <<= n_bits;
932 bitno += n_bits;
934 /*
935 * The dictionary must only be cleared at the end of a packet.
936 */
938 if (incode == CLEAR)
939 {
940 if (ilen > 0)
941 {
942 if (db->debug)
943 {
944 printk("bsd_decomp%d: bad CLEAR\n", db->unit);
945 }
946 return DECOMP_FATALERROR; /* probably a bug */
947 }
949 bsd_clear(db);
950 break;
951 }
953 if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
954 || (incode > max_ent && oldcode == CLEAR))
955 {
956 if (db->debug)
957 {
958 printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
959 db->unit, incode, oldcode);
960 printk("max_ent=0x%x explen=%d seqno=%d\n",
961 max_ent, explen, db->seqno);
962 }
963 return DECOMP_FATALERROR; /* probably a bug */
964 }
966 /* Special case for KwKwK string. */
967 if (incode > max_ent)
968 {
969 finchar = oldcode;
970 extra = 1;
971 }
972 else
973 {
974 finchar = incode;
975 extra = 0;
976 }
978 codelen = *(lens_ptr (db, finchar));
979 explen += codelen + extra;
980 if (explen > osize)
981 {
982 if (db->debug)
983 {
984 printk("bsd_decomp%d: ran out of mru\n", db->unit);
985 #ifdef DEBUG
986 printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
987 ilen, finchar, codelen, explen);
988 #endif
989 }
990 return DECOMP_FATALERROR;
991 }
993 /*
994 * Decode this code and install it in the decompressed buffer.
995 */
997 wptr += codelen;
998 p = wptr;
999 while (finchar > LAST)
1001 struct bsd_dict *dictp2 = dict_ptr (db, finchar);
1003 dictp = dict_ptr (db, dictp2->cptr);
1004 #ifdef DEBUG
1005 if (--codelen <= 0 || dictp->codem1 != finchar-1)
1007 if (codelen <= 0)
1009 printk("bsd_decomp%d: fell off end of chain ", db->unit);
1010 printk("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
1011 incode, finchar, dictp2->cptr, max_ent);
1013 else
1015 if (dictp->codem1 != finchar-1)
1017 printk("bsd_decomp%d: bad code chain 0x%x "
1018 "finchar=0x%x ",
1019 db->unit, incode, finchar);
1021 printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",
1022 oldcode, dictp2->cptr, dictp->codem1);
1025 return DECOMP_FATALERROR;
1027 #endif
1028 *--p = dictp->f.hs.suffix;
1029 finchar = dictp->f.hs.prefix;
1031 *--p = finchar;
1033 #ifdef DEBUG
1034 if (--codelen != 0)
1036 printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
1037 db->unit, codelen, incode, max_ent);
1039 #endif
1041 if (extra) /* the KwKwK case again */
1043 *wptr++ = finchar;
1046 /*
1047 * If not first code in a packet, and
1048 * if not out of code space, then allocate a new code.
1050 * Keep the hash table correct so it can be used
1051 * with uncompressed packets.
1052 */
1054 if (oldcode != CLEAR && max_ent < db->maxmaxcode)
1056 struct bsd_dict *dictp2, *dictp3;
1057 unsigned short *lens1, *lens2;
1058 unsigned long fcode;
1059 int hval, disp, indx;
1061 fcode = BSD_KEY(oldcode,finchar);
1062 hval = BSD_HASH(oldcode,finchar,db->hshift);
1063 dictp = dict_ptr (db, hval);
1065 /* look for a free hash table entry */
1066 if (dictp->codem1 < max_ent)
1068 disp = (hval == 0) ? 1 : hval;
1069 do
1071 hval += disp;
1072 if (hval >= db->hsize)
1074 hval -= db->hsize;
1076 dictp = dict_ptr (db, hval);
1078 while (dictp->codem1 < max_ent);
1081 /*
1082 * Invalidate previous hash table entry
1083 * assigned this code, and then take it over
1084 */
1086 dictp2 = dict_ptr (db, max_ent + 1);
1087 indx = dictp2->cptr;
1088 dictp3 = dict_ptr (db, indx);
1090 if (dictp3->codem1 == max_ent)
1092 dictp3->codem1 = BADCODEM1;
1095 dictp2->cptr = hval;
1096 dictp->codem1 = max_ent;
1097 dictp->f.fcode = fcode;
1098 db->max_ent = ++max_ent;
1100 /* Update the length of this string. */
1101 lens1 = lens_ptr (db, max_ent);
1102 lens2 = lens_ptr (db, oldcode);
1103 *lens1 = *lens2 + 1;
1105 /* Expand code size if needed. */
1106 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
1108 db->n_bits = ++n_bits;
1109 tgtbitno = 32-n_bits;
1112 oldcode = incode;
1115 ++db->comp_count;
1116 ++db->uncomp_count;
1117 db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;
1118 db->uncomp_bytes += explen;
1120 if (bsd_check(db))
1122 if (db->debug)
1124 printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",
1125 db->unit, db->seqno - 1);
1128 return explen;
1131 /*************************************************************
1132 * Table of addresses for the BSD compression module
1133 *************************************************************/
1135 static struct compressor ppp_bsd_compress = {
1136 .compress_proto = CI_BSD_COMPRESS,
1137 .comp_alloc = bsd_comp_alloc,
1138 .comp_free = bsd_free,
1139 .comp_init = bsd_comp_init,
1140 .comp_reset = bsd_reset,
1141 .compress = bsd_compress,
1142 .comp_stat = bsd_comp_stats,
1143 .decomp_alloc = bsd_decomp_alloc,
1144 .decomp_free = bsd_free,
1145 .decomp_init = bsd_decomp_init,
1146 .decomp_reset = bsd_reset,
1147 .decompress = bsd_decompress,
1148 .incomp = bsd_incomp,
1149 .decomp_stat = bsd_comp_stats,
1150 .owner = THIS_MODULE
1151 };
1153 /*************************************************************
1154 * Module support routines
1155 *************************************************************/
1157 static int __init bsdcomp_init(void)
1159 int answer = ppp_register_compressor(&ppp_bsd_compress);
1160 if (answer == 0)
1161 printk(KERN_INFO "PPP BSD Compression module registered\n");
1162 return answer;
1165 static void __exit bsdcomp_cleanup(void)
1167 ppp_unregister_compressor(&ppp_bsd_compress);
1170 module_init(bsdcomp_init);
1171 module_exit(bsdcomp_cleanup);
1172 MODULE_LICENSE("Dual BSD/GPL");
1173 MODULE_ALIAS("ppp-compress-" __stringify(CI_BSD_COMPRESS));