GCC Code Coverage Report

Line	Branch	Exec	Source
1			// ======================================================================
2			// \title Chunk.cpp
3			// \brief CFDP chunks (sparse gap tracking) logic file
4			//
5			// This file is a port of the cf_chunks.c file from the
6			// NASA Core Flight System (cFS) CFDP (CF) Application,
7			// version 3.0.0, adapted for use within the F-Prime (F') framework.
8			//
9			// This class handles the complexity of sparse gap tracking so that
10			// the CFDP engine doesn't need to worry about it. Information is given
11			// to the class and when needed calculations are made internally to
12			// help the engine build NAK packets. Received NAK segment requests
13			// are stored in this class as well and used for re-transmit processing.
14			//
15			// ======================================================================
16			//
17			// NASA Docket No. GSC-18,447-1
18			//
19			// Copyright (c) 2019 United States Government as represented by the
20			// Administrator of the National Aeronautics and Space Administration.
21			// All Rights Reserved.
22			//
23			// Licensed under the Apache License, Version 2.0 (the "License"); you may
24			// not use this file except in compliance with the License. You may obtain
25			// a copy of the License at
26			//
27			// http://www.apache.org/licenses/LICENSE-2.0
28			//
29			// Unless required by applicable law or agreed to in writing, software
30			// distributed under the License is distributed on an "AS IS" BASIS,
31			// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
32			// See the License for the specific language governing permissions and
33			// limitations under the License.
34			//
35			// ======================================================================
36
37			#include <string.h>
38
39			#include <Fw/Types/Assert.hpp>
40
41			#include <Svc/Ccsds/CfdpManager/Chunk.hpp>
42
43			namespace Svc {
44			namespace Ccsds {
45			namespace Cfdp {
46
47			// ======================================================================
48			// CfdpChunkList Class Implementation
49			// ======================================================================
50
51		✗	CfdpChunkList::CfdpChunkList(ChunkIdx maxChunks, Chunk* chunkMem)
52		✗	: m_count(0), m_maxChunks(maxChunks), m_chunks(chunkMem) {
53		✗	FW_ASSERT(maxChunks > 0);
54		✗	FW_ASSERT(chunkMem != nullptr);
55		✗	reset();
56		✗	}
57
58		✗	void CfdpChunkList::reset() {
59		✗	m_count = 0;
60		✗	memset(m_chunks, 0, sizeof(*m_chunks) * m_maxChunks);
61		✗	}
62
63		✗	void CfdpChunkList::add(FileSize offset, FileSize size) {
64			// A zero-length chunk covers no bytes and is not a received interval. It also violates the
65			// non-empty invariant assumed downstream by combineNext() (chunk_end > offset), so ignore it
66			// rather than asserting. This value can be derived from incoming protocol data (a FileData PDU
67			// whose payload length equals the encoded offset length), so it must not be treated as a bug.
68		✗	if (size == 0) {
69		✗	return;
70			}
71
72		✗	const Chunk chunk = {offset, size};
73		✗	const ChunkIdx i = findInsertPosition(&chunk);
74
75			// PTFO: files won't be so big we need to gracefully handle overflow,
76			// and in that case the user should change everything in chunks
77			// to use 64-bit numbers
78		✗	FW_ASSERT((offset + size) >= offset, static_cast<FwAssertArgType>(offset), static_cast<FwAssertArgType>(size));
79
80		✗	insert(i, &chunk);
81			}
82
83		✗	const Chunk* CfdpChunkList::getFirstChunk() const {
84		✗	return m_count ? &m_chunks[0] : nullptr;
85			}
86
87		✗	void CfdpChunkList::removeFromFirst(FileSize size) {
88		✗	Chunk* chunk = &m_chunks[0]; /* front is always 0 */
89
90		✗	if (size > chunk->size) {
91		✗	size = chunk->size;
92			}
93		✗	chunk->size -= size;
94
95		✗	if (!chunk->size) {
96		✗	eraseChunk(0);
97			} else {
98		✗	chunk->offset += size;
99			}
100		✗	}
101
102		✗	U32 CfdpChunkList::computeGaps(ChunkIdx maxGaps,
103			FileSize total,
104			FileSize start,
105			GapComputeCallback callback,
106			void* opaque) const {
107		✗	U32 ret = 0;
108		✗	ChunkIdx i = 0;
109			FileSize next_off;
110			FileSize gap_start;
111			Chunk chunk;
112
113			/* a zero-length file holds no data, and therefore no gaps */
114		✗	if (total == 0) {
115		✗	return 0;
116			}
117
118		✗	FW_ASSERT(start < total, static_cast<FwAssertArgType>(start), static_cast<FwAssertArgType>(total));
119
120			/* simple case: there is no chunk data, which means there is a single gap of the entire size */
121		✗	if (!m_count) {
122		✗	chunk.offset = 0;
123		✗	chunk.size = total;
124		✗	if (callback) {
125		✗	callback(&chunk, opaque);
126			}
127		✗	ret = 1;
128			} else {
129			/* Handle initial gap if needed */
130		✗	if (start < m_chunks[0].offset) {
131		✗	chunk.offset = start;
132		✗	chunk.size = m_chunks[0].offset - start;
133		✗	if (callback) {
134		✗	callback(&chunk, opaque);
135			}
136		✗	ret = 1;
137			}
138
139		✗	while ((ret < maxGaps) && (i < m_count)) {
140		✗	next_off = (i == (m_count - 1)) ? total : m_chunks[i + 1].offset;
141		✗	gap_start = (m_chunks[i].offset + m_chunks[i].size);
142
143		✗	chunk.offset = (gap_start > start) ? gap_start : start;
144		✗	chunk.size = (next_off - chunk.offset);
145
146		✗	if (gap_start >= total) {
147		✗	break;
148		✗	} else if (start < next_off) {
149			/* Only report if gap finishes after start */
150		✗	if (callback) {
151		✗	callback(&chunk, opaque);
152			}
153		✗	++ret;
154			}
155		✗	++i;
156			}
157			}
158
159		✗	return ret;
160			}
161
162		✗	void CfdpChunkList::insertChunk(ChunkIdx index, const Chunk* chunk) {
163		✗	FW_ASSERT(m_count < m_maxChunks, m_count, m_maxChunks);
164		✗	FW_ASSERT(index <= m_count, index, m_count);
165
166		✗	if (m_count && (index != m_count)) {
167		✗	memmove(&m_chunks[index + 1], &m_chunks[index], sizeof(*chunk) * (m_count - index));
168			}
169		✗	memcpy(&m_chunks[index], chunk, sizeof(*chunk));
170
171		✗	++m_count;
172		✗	}
173
174		✗	void CfdpChunkList::eraseChunk(ChunkIdx index) {
175		✗	FW_ASSERT(m_count > 0);
176		✗	FW_ASSERT(index < m_count, index, m_count);
177
178			/* to erase, move memory over the old one */
179		✗	memmove(&m_chunks[index], &m_chunks[index + 1], sizeof(*m_chunks) * (m_count - 1 - index));
180		✗	--m_count;
181		✗	}
182
183		✗	void CfdpChunkList::eraseRange(ChunkIdx start, ChunkIdx end) {
184			/* Sanity check */
185		✗	FW_ASSERT(end <= m_count, end, m_count);
186
187		✗	if (start < end) {
188		✗	memmove(&m_chunks[start], &m_chunks[end], sizeof(*m_chunks) * (m_count - end));
189		✗	m_count = static_cast<ChunkIdx>(m_count - static_cast<ChunkIdx>(end - start));
190			}
191		✗	}
192
193		✗	ChunkIdx CfdpChunkList::findInsertPosition(const Chunk* chunk) {
194		✗	ChunkIdx first = 0;
195			ChunkIdx i;
196		✗	ChunkIdx count = m_count;
197			ChunkIdx step;
198
199		✗	while (count > 0) {
200		✗	i = first;
201		✗	step = static_cast<ChunkIdx>(count / 2);
202		✗	i = static_cast<ChunkIdx>(i + step);
203		✗	if (m_chunks[i].offset < chunk->offset) {
204		✗	first = static_cast<ChunkIdx>(i + 1);
205		✗	count = static_cast<ChunkIdx>(count - static_cast<ChunkIdx>(step + 1));
206			} else {
207		✗	count = step;
208			}
209			}
210
211		✗	return first;
212			}
213
214		✗	bool CfdpChunkList::combineNext(ChunkIdx i, const Chunk* chunk) {
215		✗	ChunkIdx combined_i = i;
216		✗	bool ret = false;
217		✗	FileSize chunk_end = chunk->offset + chunk->size;
218
219			/* Assert no rollover, only possible as a bug */
220		✗	FW_ASSERT(chunk_end > chunk->offset, static_cast<FwAssertArgType>(chunk_end),
221			static_cast<FwAssertArgType>(chunk->offset));
222
223			/* Determine how many can be combined */
224		✗	for (; combined_i < m_count; ++combined_i) {
225			/* Advance combine index until there is a gap between end and the next offset */
226		✗	if (chunk_end < m_chunks[combined_i].offset) {
227		✗	break;
228			}
229			}
230
231			/* If index advanced the range of chunks can be combined */
232		✗	if (i != combined_i) {
233			/* End is the max of last combined chunk end or new chunk end */
234		✗	chunk_end = CfdpChunkMax(m_chunks[combined_i - 1].offset + m_chunks[combined_i - 1].size, chunk_end);
235
236			/* Use current slot as combined entry */
237		✗	m_chunks[i].size = chunk_end - chunk->offset;
238		✗	m_chunks[i].offset = chunk->offset;
239
240			/* Erase the rest of the combined chunks (if any) */
241		✗	eraseRange(static_cast<ChunkIdx>(i + 1), combined_i);
242		✗	ret = true;
243			}
244
245		✗	return ret;
246			}
247
248		✗	bool CfdpChunkList::combinePrevious(ChunkIdx i, const Chunk* chunk) {
249			Chunk* prev;
250			FileSize prev_end;
251			FileSize chunk_end;
252		✗	bool ret = false;
253
254		✗	FW_ASSERT(i <= m_maxChunks, i, m_maxChunks);
255
256			/* Only need to check if there is a previous */
257		✗	if (i > 0) {
258		✗	chunk_end = chunk->offset + chunk->size;
259		✗	prev = &m_chunks[i - 1];
260		✗	prev_end = prev->offset + prev->size;
261
262			/* Check if start of new chunk is less than end of previous (overlaps) */
263		✗	if (chunk->offset <= prev_end) {
264			/* When combining, use the bigger of the two endings */
265		✗	if (prev_end < chunk_end) {
266			/* Combine with previous chunk */
267		✗	prev->size = chunk_end - prev->offset;
268			}
269		✗	ret = true;
270			}
271			}
272		✗	return ret;
273			}
274
275		✗	void CfdpChunkList::insert(ChunkIdx i, const Chunk* chunk) {
276			ChunkIdx smallest_i;
277			Chunk* smallest_c;
278		✗	bool next = combineNext(i, chunk);
279			bool combined;
280
281		✗	if (next) {
282		✗	combined = combinePrevious(i, &m_chunks[i]);
283		✗	if (combined) {
284		✗	eraseChunk(i);
285			}
286			} else {
287		✗	combined = combinePrevious(i, chunk);
288		✗	if (!combined) {
289		✗	if (m_count < m_maxChunks) {
290		✗	insertChunk(i, chunk);
291			} else {
292		✗	smallest_i = findSmallestSize();
293		✗	smallest_c = &m_chunks[smallest_i];
294		✗	if (smallest_c->size < chunk->size) {
295		✗	eraseChunk(smallest_i);
296		✗	insertChunk(findInsertPosition(chunk), chunk);
297			}
298			}
299			}
300			}
301		✗	}
302
303		✗	ChunkIdx CfdpChunkList::findSmallestSize() const {
304			ChunkIdx i;
305		✗	ChunkIdx smallest = 0;
306
307		✗	for (i = 1; i < m_count; ++i) {
308		✗	if (m_chunks[i].size < m_chunks[smallest].size) {
309		✗	smallest = i;
310			}
311			}
312
313		✗	return smallest;
314			}
315
316			} // namespace Cfdp
317			} // namespace Ccsds
318			} // namespace Svc
319