mmu64: for completeness sake, define PML4_REACH (XCC)
[akaros.git] / kern / lib / circular_buffer.c
1 /* Copyright (c) 2015 Google Inc
2  * Davide Libenzi <dlibenzi@google.com>
3  * See LICENSE for details.
4  */
5
6 #include <kmalloc.h>
7 #include <string.h>
8 #include <stdio.h>
9 #include <assert.h>
10 #include <error.h>
11 #include <circular_buffer.h>
12
13 bool circular_buffer_init(struct circular_buffer *cb, size_t size, char *mem)
14 {
15         cb->mem = mem;
16         if (mem)
17                 cb->base = mem;
18         else
19                 cb->base = kmalloc(size, MEM_WAIT);
20         if (cb->base) {
21                 cb->rdptr = cb->wrptr = cb->base;
22                 cb->size = 0;
23                 cb->allocated = size;
24         }
25
26         return cb->base != NULL;
27 }
28
29 void circular_buffer_destroy(struct circular_buffer *cb)
30 {
31         if (cb->base) {
32                 if (cb->mem)
33                         kfree(cb->mem);
34                 cb->rdptr = cb->wrptr = cb->base = cb->mem = NULL;
35                 cb->size = cb->allocated = 0;
36         }
37 }
38
39 void circular_buffer_clear(struct circular_buffer *cb)
40 {
41         cb->rdptr = cb->wrptr = cb->base;
42         cb->size = 0;
43 }
44
45 static bool circular_buffer_is_overlap(const struct circular_buffer *cb,
46                                        const char *rptr, const char *wptr,
47                                        size_t size)
48 {
49         /* Check if the current write operation [wptr, wptr+size) is overwriting
50          * the block at which rptr in pointing to.
51          */
52         return (cb->size > 0) && (rptr >= wptr) && (rptr < (wptr + size));
53 }
54
55 static void circular_buffer_write_skip(struct circular_buffer *cb, char *wrptr,
56                                        size_t size)
57 {
58         /* Move the read pointer forward, so that the incoming write does not
59          * overwrite the block the read pointer is looking at.
60          */
61         while (circular_buffer_is_overlap(cb, cb->rdptr, wrptr, size)) {
62                 char *rdptr = cb->rdptr;
63                 size_t bsize = *(const cbuf_size_t *) rdptr;
64
65                 if (likely(bsize)) {
66                         cb->rdptr = rdptr + bsize;
67                         cb->size -= bsize - sizeof(cbuf_size_t);
68                         if (unlikely(cb->size == 0))
69                                 cb->rdptr = cb->base;
70                 } else {
71                         cb->rdptr = cb->base;
72                 }
73         }
74 }
75
76 size_t circular_buffer_write(struct circular_buffer *cb,
77                              const char *data, size_t size)
78 {
79         /* Data is written and evetually discarded in atomic blocks, in order to
80          * maintain the consistency of the information stored in the buffer.
81          */
82         char *wrptr = cb->wrptr;
83         size_t wspace = (cb->base + cb->allocated) - wrptr;
84         size_t esize = size + 2 * sizeof(cbuf_size_t);
85
86         if (unlikely(esize > cb->allocated))
87                 return 0;
88         /* If at the end of the buffer, the next block to be written does not fit,
89          * we move the pointer to the beginning of the circular buffer.
90          */
91         if (unlikely(esize > wspace)) {
92                 circular_buffer_write_skip(cb, wrptr, wspace);
93                 wrptr = cb->base;
94         }
95         circular_buffer_write_skip(cb, wrptr, esize);
96
97         /* Write the data and the end of sequence marker (0).
98          */
99         *(cbuf_size_t *) wrptr = sizeof(cbuf_size_t) + size;
100         memcpy(wrptr + sizeof(cbuf_size_t), data, size);
101         cb->wrptr = wrptr + sizeof(cbuf_size_t) + size;
102         cb->size += size;
103
104         *(cbuf_size_t *) cb->wrptr = 0;
105
106         return size;
107 }
108
109 size_t circular_buffer_read(struct circular_buffer *cb, char *data, size_t size,
110                             size_t off)
111 {
112         size_t asize = cb->size, rsize = 0;
113         const char *rdptr = cb->rdptr;
114
115         while (asize > 0 && size > 0) {
116                 size_t bsize = *(const cbuf_size_t *) rdptr;
117
118                 if (likely(bsize)) {
119                         size_t esize = bsize - sizeof(cbuf_size_t);
120
121                         if (off >= esize) {
122                                 off -= esize;
123                         } else {
124                                 size_t csize = MIN(esize - off, size);
125
126                                 memcpy(data, rdptr + sizeof(cbuf_size_t) + off, csize);
127                                 data += csize;
128                                 size -= csize;
129                                 rsize += csize;
130                                 off = 0;
131                         }
132                         rdptr = rdptr + bsize;
133                         asize -= esize;
134                 } else {
135                         rdptr = cb->base;
136                 }
137         }
138
139         return rsize;
140 }