1 // Copyright 2018 The Fuchsia Authors
2 //
3 // Use of this source code is governed by a MIT-style
4 // license that can be found in the LICENSE file or at
5 // https://opensource.org/licenses/MIT
6 
7 #pragma once
8 
9 #include <new>
10 #include <stdint.h>
11 #include <string.h>
12 
13 #include <fbl/algorithm.h>
14 #include <fbl/canary.h>
15 #include <fbl/intrusive_single_list.h>
16 #include <ktl/move.h>
17 #include <lib/user_copy/user_ptr.h>
18 #include <vm/page.h>
19 #include <vm/physmap.h>
20 #include <vm/pmm.h>
21 #include <zircon/types.h>
22 
23 // BufferChain is a list of fixed-size buffers allocated from the PMM.
24 //
25 // It's designed for use with channel messages.  Pages backing a BufferChain are marked as
26 // VM_PAGE_STATE_IPC.
27 //
28 // The BufferChain object itself lives *inside* its first buffer.  Here's what it looks like:
29 //
30 //   +--------------------------------+     +--------------------------------+
31 //   | page                           |     | page                           |
32 //   |+------------------------------+|     |+------------------------------+|
33 //   || Buffer                       |+---->|| Buffer                       ||
34 //   || raw_data:   +---------------+||     || raw_data:    +--------------+||
35 //   ||             |  BufferChain  |||     ||              | message data |||
36 //   || reserved -> | ~~~~~~~~~~~~~ |||     || reserved = 0 |  continued   |||
37 //   ||             |  message data |||     ||              |              |||
38 //   ||             +---------------+||     ||              +--------------+||
39 //   |+------------------------------+|     |+------------------------------+|
40 //   +--------------------------------+     +--------------------------------+
41 //
42 class BufferChain {
43 public:
44     class Buffer;
45     typedef fbl::SinglyLinkedList<Buffer*> BufferList;
46 
47     constexpr static size_t kSizeOfBuffer = PAGE_SIZE;
48     constexpr static size_t kSizeOfBufferFields = 16;
49 
50     // kRawDataSize is the maximum number of bytes that can fit in a single Buffer.
51     //
52     // However, not every Buffer in a BufferChain can store this many bytes.  The first Buffer in a
53     // BufferChain is special because it also stores the chain itself.  See also kContig.
54     constexpr static size_t kRawDataSize = kSizeOfBuffer - kSizeOfBufferFields;
55 
56     // Unfortunately, we don't yet know sizeof(BufferChain) so estimate and rely on static_asserts
57     // further down to verify.
58     constexpr static size_t kSizeOfBufferChain = sizeof(BufferList) + sizeof(list_node);
59 
60     // kContig is the number of bytes guaranteed to be stored contiguously in any buffer
61     constexpr static size_t kContig = kRawDataSize - kSizeOfBufferChain;
62 
63     // Copies |size| bytes from this chain starting at offset |src_offset| to |dst|.
64     //
65     // |src_offset| must be in the range [0, kContig).
CopyOut(user_out_ptr<void> dst,size_t src_offset,size_t size)66     zx_status_t CopyOut(user_out_ptr<void> dst, size_t src_offset, size_t size) {
67         DEBUG_ASSERT(src_offset < buffers_.front().size());
68         size_t copy_offset = src_offset;
69         size_t rem = size;
70         const auto end = buffers_.end();
71         for (auto iter = buffers_.begin(); rem > 0 && iter != end; ++iter) {
72             const size_t copy_len = fbl::min(rem, iter->size() - copy_offset);
73             const char* src = iter->data() + copy_offset;
74             const zx_status_t status = dst.copy_array_to_user(src, copy_len);
75             if (unlikely(status != ZX_OK)) {
76                 return status;
77             }
78             dst = dst.byte_offset(copy_len);
79             rem -= copy_len;
80             copy_offset = 0;
81         }
82         return ZX_OK;
83     }
84 
85     // Creates a BufferChain with enough buffers to store |size| bytes.
86     //
87     // It is the caller's responsibility to free the chain with BufferChain::Free.
88     //
89     // Returns nullptr on error.
Alloc(size_t size)90     static BufferChain* Alloc(size_t size) {
91         size += sizeof(BufferChain);
92         const size_t num_buffers = (size + kRawDataSize - 1) / kRawDataSize;
93 
94         // Allocate a list of pages.
95         list_node pages = LIST_INITIAL_VALUE(pages);
96         zx_status_t status = pmm_alloc_pages(num_buffers, 0, &pages);
97         if (unlikely(status != ZX_OK)) {
98             return nullptr;
99         }
100 
101         // Construct a Buffer in each page and add them to a temporary list.
102         BufferChain::BufferList temp;
103         vm_page_t* page;
104         list_for_every_entry (&pages, page, vm_page_t, queue_node) {
105             DEBUG_ASSERT(page->state == VM_PAGE_STATE_ALLOC);
106             page->state = VM_PAGE_STATE_IPC;
107             void* va = paddr_to_physmap(page->paddr());
108             temp.push_front(new (va) BufferChain::Buffer);
109         }
110 
111         // We now have a list of buffers and a list of pages.  Construct a chain inside the first
112         // buffer and give the buffers and pages to the chain.
113         BufferChain* chain = new (temp.front().data()) BufferChain(&temp, &pages);
114         DEBUG_ASSERT(list_is_empty(&pages));
115 
116         return chain;
117     }
118 
119     // Frees |chain| and its buffers.
Free(BufferChain * chain)120     static void Free(BufferChain* chain) {
121         // Remove the buffers and vm_page_t's from the chain *before* destroying it.
122         BufferChain::BufferList buffers(ktl::move(*chain->buffers()));
123         list_node pages = LIST_INITIAL_VALUE(pages);
124         list_move(&chain->pages_, &pages);
125 
126         chain->~BufferChain();
127 
128         while (!buffers.is_empty()) {
129             BufferChain::Buffer* buf = buffers.pop_front();
130             buf->Buffer::~Buffer();
131         }
132         pmm_free(&pages);
133     }
134 
135     // Copies |size| bytes from |src| to this chain starting at offset |dst_offset|.
136     //
137     // |dst_offset| must be in the range [0, kContig).
CopyIn(user_in_ptr<const void> src,size_t dst_offset,size_t size)138     zx_status_t CopyIn(user_in_ptr<const void> src, size_t dst_offset, size_t size) {
139         return CopyInCommon(src, dst_offset, size);
140     }
141 
142     // Same as CopyIn except |src| can be in kernel space.
143     zx_status_t CopyInKernel(const void* src, size_t dst_offset, size_t size);
144 
145     class Buffer final : public fbl::SinglyLinkedListable<Buffer*> {
146     public:
147         Buffer() = default;
148         ~Buffer() = default;
149 
data()150         char* data() {
151             canary_.Assert();
152             return raw_data_ + reserved_;
153         }
154 
size()155         size_t size() const { return sizeof(raw_data_) - reserved_; }
156 
set_reserved(uint32_t reserved)157         void set_reserved(uint32_t reserved) {
158             DEBUG_ASSERT(reserved < sizeof(raw_data_));
159             reserved_ = reserved;
160         }
161 
162     private:
163         fbl::Canary<fbl::magic("BUFC")> canary_;
164         uint32_t reserved_ = 0;
165         char raw_data_[kRawDataSize];
166     };
167     static_assert(sizeof(BufferChain::Buffer) == BufferChain::kSizeOfBuffer, "");
168 
buffers()169     BufferList* buffers() { return &buffers_; }
170 
171 private:
BufferChain(BufferList * buffers,list_node * pages)172     explicit BufferChain(BufferList* buffers, list_node* pages) {
173         buffers_.swap(*buffers);
174         list_move(pages, &pages_);
175 
176         // |this| now lives inside the first buffer.
177         buffers_.front().set_reserved(sizeof(BufferChain));
178     }
179 
~BufferChain()180     ~BufferChain() {
181         DEBUG_ASSERT(list_is_empty(&pages_));
182     }
183 
184     // |PTR_IN| is a user_in_ptr-like type.
185     template <typename PTR_IN>
CopyInCommon(PTR_IN src,size_t dst_offset,size_t size)186     zx_status_t CopyInCommon(PTR_IN src, size_t dst_offset, size_t size) {
187         DEBUG_ASSERT(dst_offset < buffers_.front().size());
188         size_t copy_offset = dst_offset;
189         size_t rem = size;
190         const auto end = buffers_.end();
191         for (auto iter = buffers_.begin(); rem > 0 && iter != end; ++iter) {
192             const size_t copy_len = fbl::min(rem, iter->size() - copy_offset);
193             char* dst = iter->data() + copy_offset;
194             const zx_status_t status = src.copy_array_from_user(dst, copy_len);
195             if (unlikely(status != ZX_OK)) {
196                 return status;
197             }
198             src = src.byte_offset(copy_len);
199             rem -= copy_len;
200             copy_offset = 0;
201         }
202         return ZX_OK;
203     }
204 
205     // Take care when adding fields as BufferChain lives inside the first buffer of buffers_.
206     BufferList buffers_;
207 
208     // pages_ is a list of vm_page_t descriptors for the pages that back BufferList.
209     list_node pages_ = LIST_INITIAL_VALUE(pages_);
210 
211     DISALLOW_COPY_ASSIGN_AND_MOVE(BufferChain);
212 };
213 static_assert(sizeof(BufferChain) == BufferChain::kSizeOfBufferChain, "");
214