1 /* @(#)buffer.c 1.32 18/08/23 Copyright 1984-2018 J. Schilling */
2 #include <schily/mconfig.h>
3 #ifndef lint
4 static UConst char sccsid[] =
5 "@(#)buffer.c 1.32 18/08/23 Copyright 1984-2018 J. Schilling";
6 #endif
7 /*
8 * Virtual storage (buffer) management.
9 *
10 * Copyright (c) 1984-2018 J. Schilling
11 */
12 /*
13 * The contents of this file are subject to the terms of the
14 * Common Development and Distribution License, Version 1.0 only
15 * (the "License"). You may not use this file except in compliance
16 * with the License.
17 *
18 * See the file CDDL.Schily.txt in this distribution for details.
19 * A copy of the CDDL is also available via the Internet at
20 * http://www.opensource.org/licenses/cddl1.txt
21 *
22 * When distributing Covered Code, include this CDDL HEADER in each
23 * file and include the License file CDDL.Schily.txt from this distribution.
24 */
25
26 /*
27 * The paged virtual memory system maintains a list of resident headers each
28 * pointing to a buffer that may be either in memory or is swapped out into
29 * the 'swapfile'. The number of resident buffers is set with 'initbuf'.
30 * There must be at least two resident buffers in order to be able to
31 * do a 'splitbuffer' operation.
32 *
33 * All used headers are in a doubly linked list. All used headers
34 * that belong to resident buffers are kept also in a second doubly linked list
35 * called the mru/lru list. This list is used to determine the buffer
36 * that (as least recently used buffer) is subject of a swap out operation.
37 *
38 * To make live easier (and avoid always to check for an empty list) at least
39 * one header is kept in the used list.
40 *
41 * Deleted headers are kept in a third list that is used to recycle then.
42 */
43
44 #include "ved.h"
45 #include "buffer.h"
46
47 LOCAL headr_t *delhead; /* Head of the linked list of deleted headers*/
48 LOCAL headr_t *mru; /* The most recently used header in memory */
49 LOCAL headr_t *lru; /* The least recently used header in memory */
50 /* All resident headers are in a chain going */
51 /* from mru to lru */
52
53 extern Uchar swapname[TMPNSIZE];
54 #ifdef __needed__
55 LOCAL FILE *readfile;
56 #endif
57 LOCAL FILE *swapfile;
58 #ifdef __needed__
59 LOCAL off_t readfoff;
60 #endif
61 LOCAL off_t swapfoff;
62 LOCAL off_t swapfend;
63 LOCAL int nbheads;
64 #ifdef DEBUG
65 LOCAL long sumsize;
66 LOCAL long sumwrite;
67 LOCAL long sumfull;
68 #endif
69 LOCAL int maxbuffers = MAXBUFFERS;
70 LOCAL int numbuffers;
71
72 EXPORT void initbuffers __PR((ewin_t *wp, int nbuf));
73 EXPORT void termbuffers __PR((ewin_t *wp));
74 LOCAL void getheader __PR((ewin_t *wp));
75 LOCAL echar_t *getbuffer __PR((ewin_t *wp));
76 LOCAL BOOL releasebuffer __PR((ewin_t *wp, headr_t *linkp));
77 EXPORT headr_t *addbuffer __PR((ewin_t *wp, headr_t *prev));
78 EXPORT headr_t *deletebuffer __PR((ewin_t *wp, headr_t *linkp));
79 EXPORT void splitbuffer __PR((ewin_t *wp, headr_t *linkp, int pos));
80 EXPORT void compressbuffer __PR((ewin_t *wp, headr_t *linkp));
81 LOCAL int bufswapin __PR((ewin_t *wp, headr_t *linkp));
82 #ifdef __needed__
83 LOCAL int bufreadin __PR((ewin_t *wp, headr_t *linkp));
84 #endif
85 EXPORT void readybuffer __PR((ewin_t *wp, headr_t *linkp));
86 LOCAL void buf_mruhead __PR((headr_t *linkp));
87 LOCAL void buf_remruhead __PR((headr_t *linkp));
88 EXPORT void bufdebug __PR((ewin_t *wp));
89
90 /*
91 * Init the paged virtual buffers.
92 * Nbuf is the number of incore buffers and may be set from the caller,
93 * if nbuf is <= 0, use the default value.
94 * The swap file file is opened and then a new (needed) buffer is added.
95 */
96 EXPORT void
initbuffers(wp,nbuf)97 initbuffers(wp, nbuf)
98 ewin_t *wp;
99 int nbuf;
100 {
101 headr_t *hp;
102
103 /*
104 * To be able to to a splitbuffer operation without copying into
105 * a temporary buffer, we need at least two incore buffers.
106 */
107 if (nbuf == 1)
108 nbuf = 2;
109 if (nbuf > 0)
110 maxbuffers = nbuf;
111 /*
112 * Open the swp file for backup memory.
113 */
114 if (swapfile == (FILE *)NULL)
115 swapfile = tmpfopen(wp, swapname, "ctwrub");
116
117 addbuffer(wp, wp->bhead);
118 /*
119 * The first valid position in buffer space is '0'.
120 * Most find operations return a position one behind the actual
121 * position making 'eof' a valid offset.
122 * To allow this to work, we make 'eof' a valid offset by inserting
123 * a dummy space at the end.
124 */
125 hp = wp->bhead;
126 hp->size = 1;
127 hp->buf[0] = ' ';
128 nbheads++;
129 }
130
131 /*
132 * Close the swapfile and delete it in preparation of an exit()
133 */
134 /* ARGSUSED */
135 EXPORT void
termbuffers(wp)136 termbuffers(wp)
137 ewin_t *wp;
138 {
139 if (--nbheads > 0) {
140 /*
141 * Wenn mehrere Files unterst�tzt werden,
142 * dann wird hier der Speicher zur�ckgegeben.
143 */
144 /*EMPTY*/
145 }
146 if (nbheads == 0) {
147 if (swapfile)
148 fclose(swapfile);
149 if (swapname[0] != '\0')
150 unlink(C swapname);
151 }
152
153 #ifdef DEBUG
154 if (sumwrite)cdbg("nwrite: %ld nfull: %ld avgsize: %ld (%ld%%)",
155 sumwrite, sumfull, sumsize/sumwrite, sumsize/BUFFERSIZE*100/sumwrite);
156 #endif
157 }
158
159 /*
160 * Get a new header.
161 * Try to use a recycled header if possible,
162 * else get some new headers and give them new swap file positions.
163 */
164 LOCAL void
getheader(wp)165 getheader(wp)
166 ewin_t *wp;
167 {
168 register headr_t *hp;
169 static int amt = 32;
170 register int i = amt;
171
172 if (amt < 256)
173 amt *= 2;
174
175 if ((delhead = (headr_t *) malloc(i*sizeof (headr_t))) == NULL) {
176 rsttmodes(wp);
177 raisecond("Out of memory", 0);
178 }
179
180 hp = delhead;
181 hp->next = hp;
182
183 while (--i > 0) {
184 hp = hp->next;
185 hp->buf = hp->cont = NULL;
186 hp->fpos = swapfend;
187 hp->size = 0;
188 hp->flags = 0;
189 hp->next = &hp[1];
190 swapfend += BUFFERSIZE;
191 }
192 hp->next = (headr_t *)0;
193 }
194
195 /*
196 * Get a buffer.
197 * If we are below the buffer limit, allocate a new one, else try to release
198 * one of the buffers currently in use. The buffer to be released in this
199 * case is the first in the least recently used chain.
200 */
201 LOCAL echar_t *
getbuffer(wp)202 getbuffer(wp)
203 ewin_t *wp;
204 {
205 register headr_t *linkp = lru;
206 echar_t *buf;
207
208 #ifdef DEBUG
209 cdbg("getbuffer()");
210 #endif
211 if (numbuffers >= maxbuffers) {
212 if (linkp == (headr_t *)0) {
213 rsttmodes(wp);
214 raisecond("Incore buffer lost", 0);
215 }
216 if (releasebuffer(wp, linkp)) {
217 buf = linkp->buf;
218 linkp->buf = linkp->cont = NULL;
219 linkp->flags &= ~INMEMORY;
220 buf_remruhead(linkp);
221 #ifdef DEBUG
222 cdbg("getbuffer() = %p", (void *)linkp->buf);
223 #endif
224 return (buf);
225 }
226 }
227 if ((buf = (echar_t *) malloc(BUFFERSIZE * sizeof (echar_t))) == 0) {
228 rsttmodes(wp);
229 raisecond("Out of memory", 0);
230 }
231 numbuffers++;
232 #ifdef DEBUG
233 cdbg("getbuffer() = %p", (void *)buf);
234 #endif
235 return (buf);
236 }
237
238 /*
239 * Release the buffer associated with a header.
240 * If the buffer is modified, back it up to the swapfile before.
241 */
242 LOCAL BOOL
releasebuffer(wp,linkp)243 releasebuffer(wp, linkp)
244 ewin_t *wp;
245 register headr_t *linkp;
246 {
247 #ifdef DEBUG
248 cdbg("releasebuffer(%p)", (void *)linkp);
249 #endif
250 if ((linkp->flags & INMEMORY) == 0)
251 return (TRUE);
252 if ((linkp->flags & MODIFIED) == 0)
253 return (TRUE);
254 #ifdef DEBUG
255 writecons("write");
256 #endif
257 #ifdef DEBUG
258 if (linkp->size != BUFFERSIZE)
259 cdbg("pos: %lld size: %d", (Llong)linkp->fpos, linkp->size);
260 else sumfull++;
261 sumwrite++;
262 sumsize += linkp->size;
263 #endif
264 /*
265 * Try to avoid seeks if possible.
266 */
267 if (swapfoff != linkp->fpos)
268 lseek(fdown(swapfile), linkp->fpos, SEEK_SET);
269 if (writesyserr(wp, swapfile, linkp->cont, linkp->size, swapname) < 0) {
270 swapfoff = (off_t)-1;
271 return (FALSE);
272 }
273 swapfoff = linkp->fpos + linkp->size;
274 linkp->flags &= ~MODIFIED;
275 linkp->flags |= ONSWAP;
276 return (TRUE);
277 }
278
279 /*
280 * Read a buffer from the swapfile.
281 */
282 LOCAL int
bufswapin(wp,linkp)283 bufswapin(wp, linkp)
284 ewin_t *wp;
285 register headr_t *linkp;
286 {
287 /*
288 * Try to avoid seeks if possible.
289 */
290 if (swapfoff != linkp->fpos)
291 lseek(fdown(swapfile), linkp->fpos, SEEK_SET);
292 if (readsyserr(wp, swapfile, linkp->cont, linkp->size, swapname) < 0) {
293 swapfoff = (off_t)-1;
294 return (-1);
295 } else {
296 swapfoff = linkp->fpos + linkp->size;
297 }
298 linkp->flags |= INMEMORY;
299 return (0);
300 }
301
302 #ifdef __needed__
303 /*
304 * Read a buffer from the original file.
305 * Used in case that the original file was not read into the swapfile when
306 * starting to edit a new file.
307 */
308 LOCAL int
bufreadin(wp,linkp)309 bufreadin(wp, linkp)
310 ewin_t *wp;
311 register headr_t *linkp;
312 {
313 /*
314 * Try to avoid seeks if possible.
315 */
316 if (readfoff != linkp->fpos)
317 lseek(fdown(readfile), linkp->fpos, SEEK_SET);
318 /*XXX*/
319 if (readsyserr(wp, readfile, linkp->cont, linkp->size, wp->curfile) < 0) {
320 readfoff = (off_t)-1;
321 return (-1);
322 } else {
323 readfoff = linkp->fpos + linkp->size;
324 }
325 linkp->flags |= INMEMORY;
326 return (0);
327 }
328 #endif
329
330 /*
331 * Make the buffer for a header ready to use
332 * by swapping in the data from the swap file if needed.
333 * Make it the most recently used one.
334 */
335 EXPORT void
readybuffer(wp,linkp)336 readybuffer(wp, linkp)
337 ewin_t *wp;
338 register headr_t *linkp;
339 {
340 #ifdef DEBUG
341 cdbg("readybuffer(%p)", (void *)linkp);
342 #endif
343 if ((linkp->flags & INMEMORY) == 0) {
344 #ifdef DEBUG
345 writecons("read");
346 #endif
347 linkp->cont = linkp->buf = getbuffer(wp);
348 if (linkp->flags & INVALID) {
349 linkp->flags &= ~INVALID;
350 linkp->flags |= INMEMORY;
351 } else {
352 bufswapin(wp, linkp);
353 }
354 }
355 buf_mruhead(linkp);
356 }
357
358 /*
359 * Add a new header and an associated buffer after 'prev' header.
360 * Add the new header to the linked list of the used headers as well as to
361 * the mru/lru chain by making it the most recently used one.
362 * If 'prev' is NULL, add the new header to the head of the header chain.
363 * Getting a new buffer for the new header is handled by getbuffer().
364 * If no memory could be allocated, raise a software signal and return NULL.
365 */
366 EXPORT headr_t *
addbuffer(wp,prev)367 addbuffer(wp, prev)
368 ewin_t *wp;
369 headr_t *prev;
370 {
371 register headr_t *newlinkp = NULL;
372 register headr_t *next;
373 #ifdef DEBUG
374 cdbg("addbuffer(%p)", (void *)prev);
375 #endif
376
377 if (prev) {
378 next = prev->next;
379 } else {
380 next = wp->bhead;
381 }
382
383 if (delhead == (headr_t *)0)
384 getheader(wp);
385
386 newlinkp = delhead;
387 delhead = newlinkp->next;
388
389 if (newlinkp->fpos == (off_t)-1) {
390 newlinkp->fpos = swapfend;
391 swapfend += BUFFERSIZE;
392 }
393
394 if ((newlinkp->cont = newlinkp->buf = getbuffer(wp)) == NULL) {
395 newlinkp->flags = INVALID;
396 newlinkp->next = delhead;
397 delhead = newlinkp;
398 return ((headr_t *)0);
399 }
400 newlinkp->flags = (INMEMORY|MODIFIED); /* make shure to swap out */
401 /* at the first time */
402 #ifdef DEBUG
403 cdbg("New Link: %p", (void *)newlinkp);
404 #endif
405 newlinkp->size = 0;
406 newlinkp->nextr = newlinkp->prevr = (headr_t *)0;
407 newlinkp->next = next;
408 if (next)
409 next->prev = newlinkp;
410 newlinkp->prev = prev;
411 if (prev) {
412 prev->next = newlinkp;
413 } else {
414 wp->bhead = newlinkp;
415 }
416 buf_mruhead(newlinkp);
417 return (newlinkp);
418 }
419
420 /*
421 * Delete the header 'linkp' and its associated buffer if 'linkp' is not the
422 * only header. Remove it from the header chain and from the mru/lru chain.
423 * If there was only one header return it, else return 'linkp->prev'.
424 */
425 EXPORT headr_t *
deletebuffer(wp,linkp)426 deletebuffer(wp, linkp)
427 ewin_t *wp;
428 register headr_t *linkp;
429 {
430 headr_t *next = linkp->next;
431 headr_t *prev = linkp->prev;
432 #ifdef DEBUG
433 cdbg("deletebuffer(%p)", (void *)linkp);
434 #endif
435
436 if (next || prev) {
437 /*
438 * 'linkp' is not the only header,
439 * remove it from the mru/lru chain and
440 * from the active header chain.
441 */
442 buf_remruhead(linkp);
443 if (next) {
444 next->prev = prev;
445 }
446 if (prev) {
447 prev->next = next;
448 } else {
449 wp->bhead = next;
450 }
451 /*
452 * Free the associated buffer
453 */
454 if (linkp->flags & INMEMORY) {
455 free(linkp->buf);
456 linkp->buf = linkp->cont = NULL;
457 numbuffers--;
458 }
459 /*
460 * Mark as deleted and add header to linked dels
461 */
462 linkp->flags = INVALID;
463 linkp->next = delhead;
464 delhead = linkp;
465 clearifwpos(wp, linkp);
466 return (prev);
467 } else {
468 /*
469 * Keep at least one header
470 */
471 linkp->size = 0;
472 linkp->cont = linkp->buf;
473 return (linkp);
474 }
475 }
476
477 /*
478 * Split a buffer into two buffers starting at offset 'pos' in the buffer.
479 * Used by movegap() to prepare insert or delete operations.
480 * Pos will be the first unused element in the current buffer after
481 * the split is done.
482 * If the current buffer ends before pos, we are done,
483 * else insert a new buffer and copy the rest to the new buffer.
484 * Put a gap at the beginning of the new buffer.
485 */
486 EXPORT void
splitbuffer(wp,linkp,pos)487 splitbuffer(wp, linkp, pos)
488 ewin_t *wp;
489 register headr_t *linkp;
490 int pos;
491 {
492 register headr_t *newlinkp = NULL;
493 register echar_t *from;
494 register echar_t *to;
495 echar_t *end;
496 int newsize = linkp->size - pos;
497
498 #ifdef DEBUG
499 cdbg("splitbuffer(%p, %d)", (void *)linkp, pos);
500 #endif
501 if (newsize <= 0)
502 return;
503 readybuffer(wp, linkp);
504 newlinkp = addbuffer(wp, linkp);
505
506 end = newlinkp->buf + BUFFERSIZE;
507 newlinkp->size = newsize;
508 newlinkp->cont = end - newsize;
509 linkp->size = pos;
510
511 from = linkp->cont + pos;
512 to = newlinkp->cont;
513 if (newsize > 16) {
514 movebytes(C from, C to, newsize * sizeof (echar_t));
515 } else while (to < end) {
516 *to++ = *from++;
517 }
518 }
519
520 /*
521 * Compress the content of a buffer.
522 * Remove a leading gap and then try to combine its content with
523 * the content of the next buffer.
524 * Loop until the next buffer has no leading gap.
525 */
526 EXPORT void
compressbuffer(wp,linkp)527 compressbuffer(wp, linkp)
528 ewin_t *wp;
529 register headr_t *linkp;
530 {
531 register echar_t *from;
532 register echar_t *to;
533 echar_t *end;
534 register headr_t *next;
535
536 again:
537
538 #ifdef DEBUG
539 cdbg("compressbuffer(%p)", (void *)linkp);
540 #endif
541 if (linkp == (headr_t *)0)
542 return;
543 readybuffer(wp, linkp);
544
545 /*
546 * First, remove a leading gap if present.
547 */
548 if ((from = linkp->cont) != (to = linkp->buf)) {
549 linkp->flags |= MODIFIED;
550 if (linkp->size > 16) {
551 movebytes(C from, C to, linkp->size * sizeof (echar_t));
552 } else {
553 end = to + linkp->size;
554 while (to < end)
555 *to++ = *from++;
556 }
557 }
558 linkp->cont = linkp->buf;
559
560 while ((next = linkp->next) != NULL &&
561 (linkp->size+next->size <= BUFFERSIZE)) {
562
563 /*
564 * If the buffer from 'linkp' and the next buffer or one of the
565 * following buffers can be combined, do it.
566 */
567 readybuffer(wp, next);
568 from = next->cont;
569 to = linkp->cont + linkp->size;
570 linkp->flags |= MODIFIED;
571 if (next->size > 16) {
572 movebytes(C from, C to, next->size * sizeof (echar_t));
573 } else {
574 end = from + next->size;
575 while (from < end)
576 *to++ = *from++;
577 }
578 linkp->size += next->size;
579
580 /*
581 * Delete the now unused buffer.
582 */
583 deletebuffer(wp, next);
584 }
585
586 /*
587 * If the next buffer has a leading gap, compress it too.
588 */
589 if ((next = linkp->next) != NULL && (next->cont != next->buf)) {
590 linkp = next;
591 goto again;
592 }
593 }
594
595 /*
596 * Make 'linkp' the most recently used header
597 */
598 LOCAL void
buf_mruhead(linkp)599 buf_mruhead(linkp)
600 register headr_t *linkp;
601 {
602 /*
603 * If linkp is already the most recently used header, we are done.
604 */
605 if (mru == linkp)
606 return;
607
608 /*
609 * First remove it from the mru/lru chain.
610 * This will also maintain the lru pointer.
611 */
612 buf_remruhead(linkp);
613
614 /*
615 * Actually make it the most recently used one.
616 */
617 linkp->prevr = mru;
618 linkp->nextr = (headr_t *)0;
619 if (mru != (headr_t *)0)
620 mru->nextr = linkp;
621 mru = linkp;
622
623 /*
624 * If the list was empty before,
625 * it is the least recently used header too.
626 */
627 if (lru == (headr_t *)0)
628 lru = linkp;
629 }
630
631 /*
632 * Remove a header from the mru/lru chain.
633 * May be called even if the header is not in the mru/lru chain.
634 */
635 LOCAL void
buf_remruhead(linkp)636 buf_remruhead(linkp)
637 register headr_t *linkp;
638 {
639 register headr_t *nextr = linkp->nextr;
640 register headr_t *prevr = linkp->prevr;
641
642 if (mru == linkp)
643 mru = prevr;
644 if (lru == linkp)
645 lru = nextr;
646 /*
647 * If it is not the first or the last in the chain, remove it.
648 */
649 if (nextr) {
650 nextr->prevr = prevr;
651 linkp->nextr = (headr_t *)0;
652 }
653 if (prevr) {
654 prevr->nextr = nextr;
655 linkp->prevr = (headr_t *)0;
656 }
657 }
658
659 /*#define DEBUG*/
660 #ifdef DEBUG
661
662 /*
663 * Print buffer debug statistics
664 */
665 EXPORT void
bufdebug(wp)666 bufdebug(wp)
667 ewin_t *wp;
668 {
669 long i = 0;
670 headr_t *p = wp->bhead;
671
672 while (p) {
673 i++;
674 p = p->next;
675 }
676 p = wp->bhead;
677 cdbg("h->size: %d n: %ld", p->size, i);
678 if (p->next)
679 cdbg("h->next->size: %d", p->next->size);
680 }
681
682 #else
683
684 /* ARGSUSED */
685 EXPORT void
bufdebug(wp)686 bufdebug(wp)
687 ewin_t *wp;
688 {
689 }
690
691 #endif
692