1 /*
2 * Copyright (c) 2018 Nordic Semiconductor ASA
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #include <zephyr/shell/shell_history.h>
8 #include <string.h>
9
10 /*
11 * History must store strings (commands) and allow traversing them and adding
12 * new string. When new item is added then first it is compared if it is not
13 * the same as the last one (then it is not stored). If there is no room in the
14 * buffer to store the new item, oldest one is removed until there is a room.
15 *
16 * Items are allocated and stored in the ring buffer. Items then a linked in
17 * the list.
18 *
19 * Because stored strings must be copied and compared, it is more convenient to
20 * store them in the ring buffer in a way that they are not split into two
21 * chunks (when ring buffer wraps). To ensure that item is in a single chunk,
22 * item includes padding. If continues area for new item cannot be allocated
23 * then allocated space is increased by the padding.
24 *
25 * If item does not fit at the end of the ring buffer padding is added: *
26 * +-----------+----------------+-----------------------------------+---------+
27 * | header | "history item" | | padding |
28 * | padding | | | |
29 * +-----------+----------------+-----------------------------------+---------+
30 *
31 * If item fits in the ring buffer available space then there is no padding:
32 * +-----------------+------------+----------------+--------------------------+
33 * | | header | "history item" | |
34 * | | no padding | | |
35 * +-----------------+------------+----------------+--------------------------+
36 *
37 * As an optimization, the added padding is attributed to the preceding item
38 * instead of the current item. This way the padding will be freed one item
39 * sooner.
40 */
41 struct shell_history_item {
42 sys_dnode_t dnode;
43 uint16_t len;
44 uint16_t padding;
45 char data[0];
46 };
47
z_shell_history_mode_exit(struct shell_history * history)48 void z_shell_history_mode_exit(struct shell_history *history)
49 {
50 history->current = NULL;
51 }
52
z_shell_history_get(struct shell_history * history,bool up,uint8_t * dst,uint16_t * len)53 bool z_shell_history_get(struct shell_history *history, bool up,
54 uint8_t *dst, uint16_t *len)
55 {
56 struct shell_history_item *h_item; /* history item */
57 sys_dnode_t *l_item; /* list item */
58
59 if (sys_dlist_is_empty(&history->list)) {
60 *len = 0U;
61 return false;
62 }
63
64 if (!up) { /* button down */
65 if (history->current == NULL) {
66 /* Not in history mode. It is started by up button. */
67 *len = 0U;
68
69 return false;
70 }
71
72 l_item = sys_dlist_peek_prev_no_check(&history->list,
73 history->current);
74 } else { /* button up */
75 l_item = (history->current == NULL) ?
76 sys_dlist_peek_head_not_empty(&history->list) :
77 sys_dlist_peek_next_no_check(&history->list, history->current);
78
79 }
80
81 history->current = l_item;
82 h_item = CONTAINER_OF(l_item, struct shell_history_item, dnode);
83
84 if (l_item) {
85 memcpy(dst, h_item->data, h_item->len);
86 *len = h_item->len;
87 dst[*len] = '\0';
88 return true;
89 }
90
91 *len = 0U;
92 return false;
93 }
94
add_to_head(struct shell_history * history,struct shell_history_item * item,uint8_t * src,size_t len,uint16_t padding)95 static void add_to_head(struct shell_history *history,
96 struct shell_history_item *item,
97 uint8_t *src, size_t len, uint16_t padding)
98 {
99 item->len = len;
100 item->padding = padding;
101 memcpy(item->data, src, len);
102 sys_dlist_prepend(&history->list, &item->dnode);
103 }
104
105 /* Returns true if element was removed. */
remove_from_tail(struct shell_history * history)106 static bool remove_from_tail(struct shell_history *history)
107 {
108 sys_dnode_t *l_item; /* list item */
109 struct shell_history_item *h_item;
110 uint32_t total_len;
111
112 if (sys_dlist_is_empty(&history->list)) {
113 return false;
114 }
115
116 l_item = sys_dlist_peek_tail(&history->list);
117 sys_dlist_remove(l_item);
118
119 h_item = CONTAINER_OF(l_item, struct shell_history_item, dnode);
120
121 total_len = offsetof(struct shell_history_item, data) +
122 h_item->len + h_item->padding;
123 ring_buf_get(history->ring_buf, NULL, total_len);
124
125 return true;
126 }
127
z_shell_history_purge(struct shell_history * history)128 void z_shell_history_purge(struct shell_history *history)
129 {
130 while (remove_from_tail(history)) {
131 }
132 }
133
z_shell_history_put(struct shell_history * history,uint8_t * line,size_t len)134 void z_shell_history_put(struct shell_history *history, uint8_t *line,
135 size_t len)
136 {
137 sys_dnode_t *l_item; /* list item */
138 struct shell_history_item *h_item, *h_prev_item;
139 uint32_t total_len = len + offsetof(struct shell_history_item, data);
140 uint32_t claim_len;
141 uint32_t claim2_len;
142 uint16_t padding = (~total_len + 1) & (sizeof(void *) - 1);
143
144 /* align to word. */
145 total_len += padding;
146
147 if (total_len > ring_buf_capacity_get(history->ring_buf)) {
148 return;
149 }
150
151 z_shell_history_mode_exit(history);
152
153 if (len == 0) {
154 return;
155 }
156
157 l_item = sys_dlist_peek_head(&history->list);
158 h_prev_item = CONTAINER_OF(l_item, struct shell_history_item, dnode);
159
160 if (l_item &&
161 (h_prev_item->len == len) &&
162 (memcmp(h_prev_item->data, line, len) == 0)) {
163 /* Same command as before, do not store */
164 return;
165 }
166
167 do {
168 if (ring_buf_is_empty(history->ring_buf)) {
169 /* if history is empty reset ring buffer. Even when
170 * ring buffer is empty, it is possible that available
171 * continues memory in worst case equals half of the
172 * ring buffer capacity. By resetting ring buffer we
173 * ensure that it is capable to provide continues memory
174 * of ring buffer capacity length.
175 */
176 ring_buf_reset(history->ring_buf);
177 }
178
179 claim_len = ring_buf_put_claim(history->ring_buf,
180 (uint8_t **)&h_item, total_len);
181 /* second allocation may succeed if we were at the end of the
182 * buffer.
183 */
184 if (claim_len < total_len) {
185 claim2_len =
186 ring_buf_put_claim(history->ring_buf,
187 (uint8_t **)&h_item, total_len);
188 if (claim2_len == total_len) {
189 /*
190 * We may get here only if a previous entry
191 * exists. Stick the excess padding to it.
192 */
193 h_prev_item->padding += claim_len;
194 total_len += claim_len;
195 claim_len = total_len;
196 }
197 }
198
199 if (claim_len == total_len) {
200 add_to_head(history, h_item, line, len, padding);
201 ring_buf_put_finish(history->ring_buf, claim_len);
202 break;
203 }
204
205 ring_buf_put_finish(history->ring_buf, 0);
206 remove_from_tail(history);
207 } while (1);
208 }
209
z_shell_history_init(struct shell_history * history)210 void z_shell_history_init(struct shell_history *history)
211 {
212 sys_dlist_init(&history->list);
213 history->current = NULL;
214 }
215
