1/* 2 * Message Processing Stack, Reader implementation 3 * 4 * Copyright The Mbed TLS Contributors 5 * SPDX-License-Identifier: Apache-2.0 6 * 7 * Licensed under the Apache License, Version 2.0 (the "License"); you may 8 * not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 * 19 * This file is part of Mbed TLS (https://tls.mbed.org) 20 */ 21 22#include "common.h" 23 24#if defined(MBEDTLS_SSL_PROTO_TLS1_3) 25 26#include "mps_reader.h" 27#include "mps_common.h" 28#include "mps_trace.h" 29 30#include <string.h> 31 32#if defined(MBEDTLS_MPS_ENABLE_TRACE) 33static int mbedtls_mps_trace_id = MBEDTLS_MPS_TRACE_BIT_READER; 34#endif /* MBEDTLS_MPS_ENABLE_TRACE */ 35 36/* 37 * GENERAL NOTE ON CODING STYLE 38 * 39 * The following code intentionally separates memory loads 40 * and stores from other operations (arithmetic or branches). 41 * This leads to the introduction of many local variables 42 * and significantly increases the C-code line count, but 43 * should not increase the size of generated assembly. 44 * 45 * The reason for this is twofold: 46 * (1) It will ease verification efforts using the VST 47 * (Verified Software Toolchain) 48 * whose program logic cannot directly reason 49 * about instructions containing a load or store in 50 * addition to other operations (e.g. *p = *q or 51 * tmp = *p + 42). 52 * (2) Operating on local variables and writing the results 53 * back to the target contexts on success only 54 * allows to maintain structure invariants even 55 * on failure - this in turn has two benefits: 56 * (2.a) If for some reason an error code is not caught 57 * and operation continues, functions are nonetheless 58 * called with sane contexts, reducing the risk 59 * of dangerous behavior. 60 * (2.b) Randomized testing is easier if structures 61 * remain intact even in the face of failing 62 * and/or non-sensical calls. 63 * Moreover, it might even reduce code-size because 64 * the compiler need not write back temporary results 65 * to memory in case of failure. 66 * 67 */ 68 69static inline int mps_reader_is_accumulating( 70 mbedtls_mps_reader const *rd) 71{ 72 mbedtls_mps_size_t acc_remaining; 73 if (rd->acc == NULL) { 74 return 0; 75 } 76 77 acc_remaining = rd->acc_share.acc_remaining; 78 return acc_remaining > 0; 79} 80 81static inline int mps_reader_is_producing( 82 mbedtls_mps_reader const *rd) 83{ 84 unsigned char *frag = rd->frag; 85 return frag == NULL; 86} 87 88static inline int mps_reader_is_consuming( 89 mbedtls_mps_reader const *rd) 90{ 91 return !mps_reader_is_producing(rd); 92} 93 94static inline mbedtls_mps_size_t mps_reader_get_fragment_offset( 95 mbedtls_mps_reader const *rd) 96{ 97 unsigned char *acc = rd->acc; 98 mbedtls_mps_size_t frag_offset; 99 100 if (acc == NULL) { 101 return 0; 102 } 103 104 frag_offset = rd->acc_share.frag_offset; 105 return frag_offset; 106} 107 108static inline mbedtls_mps_size_t mps_reader_serving_from_accumulator( 109 mbedtls_mps_reader const *rd) 110{ 111 mbedtls_mps_size_t frag_offset, end; 112 113 frag_offset = mps_reader_get_fragment_offset(rd); 114 end = rd->end; 115 116 return end < frag_offset; 117} 118 119static inline void mps_reader_zero(mbedtls_mps_reader *rd) 120{ 121 /* A plain memset() would likely be more efficient, 122 * but the current way of zeroing makes it harder 123 * to overlook fields which should not be zero-initialized. 124 * It's also more suitable for FV efforts since it 125 * doesn't require reasoning about structs being 126 * interpreted as unstructured binary blobs. */ 127 static mbedtls_mps_reader const zero = 128 { .frag = NULL, 129 .frag_len = 0, 130 .commit = 0, 131 .end = 0, 132 .pending = 0, 133 .acc = NULL, 134 .acc_len = 0, 135 .acc_available = 0, 136 .acc_share = { .acc_remaining = 0 } }; 137 *rd = zero; 138} 139 140int mbedtls_mps_reader_init(mbedtls_mps_reader *rd, 141 unsigned char *acc, 142 mbedtls_mps_size_t acc_len) 143{ 144 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_init"); 145 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 146 "* Accumulator size: %u bytes", (unsigned) acc_len); 147 mps_reader_zero(rd); 148 rd->acc = acc; 149 rd->acc_len = acc_len; 150 MBEDTLS_MPS_TRACE_RETURN(0); 151} 152 153int mbedtls_mps_reader_free(mbedtls_mps_reader *rd) 154{ 155 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_free"); 156 mps_reader_zero(rd); 157 MBEDTLS_MPS_TRACE_RETURN(0); 158} 159 160int mbedtls_mps_reader_feed(mbedtls_mps_reader *rd, 161 unsigned char *new_frag, 162 mbedtls_mps_size_t new_frag_len) 163{ 164 mbedtls_mps_size_t copy_to_acc; 165 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_feed"); 166 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 167 "* Fragment length: %u bytes", (unsigned) new_frag_len); 168 169 if (new_frag == NULL) { 170 MBEDTLS_MPS_TRACE_RETURN(MBEDTLS_ERR_MPS_READER_INVALID_ARG); 171 } 172 173 MBEDTLS_MPS_STATE_VALIDATE_RAW(mps_reader_is_producing( 174 rd), 175 "mbedtls_mps_reader_feed() requires reader to be in producing mode"); 176 177 if (mps_reader_is_accumulating(rd)) { 178 unsigned char *acc = rd->acc; 179 mbedtls_mps_size_t acc_remaining = rd->acc_share.acc_remaining; 180 mbedtls_mps_size_t acc_available = rd->acc_available; 181 182 /* Skip over parts of the accumulator that have already been filled. */ 183 acc += acc_available; 184 185 copy_to_acc = acc_remaining; 186 if (copy_to_acc > new_frag_len) { 187 copy_to_acc = new_frag_len; 188 } 189 190 /* Copy new contents to accumulator. */ 191 memcpy(acc, new_frag, copy_to_acc); 192 193 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 194 "Copy new data of size %u of %u into accumulator at offset %u", 195 (unsigned) copy_to_acc, (unsigned) new_frag_len, 196 (unsigned) acc_available); 197 198 /* Check if, with the new fragment, we have enough data. */ 199 acc_remaining -= copy_to_acc; 200 if (acc_remaining > 0) { 201 /* We need to accumulate more data. Stay in producing mode. */ 202 acc_available += copy_to_acc; 203 rd->acc_share.acc_remaining = acc_remaining; 204 rd->acc_available = acc_available; 205 MBEDTLS_MPS_TRACE_RETURN(MBEDTLS_ERR_MPS_READER_NEED_MORE); 206 } 207 208 /* We have filled the accumulator: Move to consuming mode. */ 209 210 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 211 "Enough data available to serve user request"); 212 213 /* Remember overlap of accumulator and fragment. */ 214 rd->acc_share.frag_offset = acc_available; 215 acc_available += copy_to_acc; 216 rd->acc_available = acc_available; 217 } else { /* Not accumulating */ 218 rd->acc_share.frag_offset = 0; 219 } 220 221 rd->frag = new_frag; 222 rd->frag_len = new_frag_len; 223 rd->commit = 0; 224 rd->end = 0; 225 MBEDTLS_MPS_TRACE_RETURN(0); 226} 227 228 229int mbedtls_mps_reader_get(mbedtls_mps_reader *rd, 230 mbedtls_mps_size_t desired, 231 unsigned char **buffer, 232 mbedtls_mps_size_t *buflen) 233{ 234 unsigned char *frag; 235 mbedtls_mps_size_t frag_len, frag_offset, end, frag_fetched, frag_remaining; 236 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_get"); 237 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 238 "* Bytes requested: %u", (unsigned) desired); 239 240 MBEDTLS_MPS_STATE_VALIDATE_RAW(mps_reader_is_consuming( 241 rd), 242 "mbedtls_mps_reader_get() requires reader to be in consuming mode"); 243 244 end = rd->end; 245 frag_offset = mps_reader_get_fragment_offset(rd); 246 247 /* Check if we're still serving from the accumulator. */ 248 if (mps_reader_serving_from_accumulator(rd)) { 249 /* Illustration of supported and unsupported cases: 250 * 251 * - Allowed #1 252 * 253 * +-----------------------------------+ 254 * | frag | 255 * +-----------------------------------+ 256 * 257 * end end+desired 258 * | | 259 * +-----v-------v-------------+ 260 * | acc | 261 * +---------------------------+ 262 * | | 263 * frag_offset acc_available 264 * 265 * - Allowed #2 266 * 267 * +-----------------------------------+ 268 * | frag | 269 * +-----------------------------------+ 270 * 271 * end end+desired 272 * | | 273 * +----------v----------------v 274 * | acc | 275 * +---------------------------+ 276 * | | 277 * frag_offset acc_available 278 * 279 * - Not allowed #1 (could be served, but we don't actually use it): 280 * 281 * +-----------------------------------+ 282 * | frag | 283 * +-----------------------------------+ 284 * 285 * end end+desired 286 * | | 287 * +------v-------------v------+ 288 * | acc | 289 * +---------------------------+ 290 * | | 291 * frag_offset acc_available 292 * 293 * 294 * - Not allowed #2 (can't be served with a contiguous buffer): 295 * 296 * +-----------------------------------+ 297 * | frag | 298 * +-----------------------------------+ 299 * 300 * end end + desired 301 * | | 302 * +------v--------------------+ v 303 * | acc | 304 * +---------------------------+ 305 * | | 306 * frag_offset acc_available 307 * 308 * In case of Allowed #2 we're switching to serve from 309 * `frag` starting from the next call to mbedtls_mps_reader_get(). 310 */ 311 312 unsigned char *acc; 313 314 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 315 "Serve the request from the accumulator"); 316 if (frag_offset - end < desired) { 317 mbedtls_mps_size_t acc_available; 318 acc_available = rd->acc_available; 319 if (acc_available - end != desired) { 320 /* It might be possible to serve some of these situations by 321 * making additional space in the accumulator, removing those 322 * parts that have already been committed. 323 * On the other hand, this brings additional complexity and 324 * enlarges the code size, while there doesn't seem to be a use 325 * case where we don't attempt exactly the same `get` calls when 326 * resuming on a reader than what we tried before pausing it. 327 * If we believe we adhere to this restricted usage throughout 328 * the library, this check is a good opportunity to 329 * validate this. */ 330 MBEDTLS_MPS_TRACE_RETURN( 331 MBEDTLS_ERR_MPS_READER_INCONSISTENT_REQUESTS); 332 } 333 } 334 335 acc = rd->acc; 336 acc += end; 337 338 *buffer = acc; 339 if (buflen != NULL) { 340 *buflen = desired; 341 } 342 343 end += desired; 344 rd->end = end; 345 rd->pending = 0; 346 347 MBEDTLS_MPS_TRACE_RETURN(0); 348 } 349 350 /* Attempt to serve the request from the current fragment */ 351 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 352 "Serve the request from the current fragment."); 353 354 frag_len = rd->frag_len; 355 frag_fetched = end - frag_offset; /* The amount of data from the current 356 * fragment that has already been passed 357 * to the user. */ 358 frag_remaining = frag_len - frag_fetched; /* Remaining data in fragment */ 359 360 /* Check if we can serve the read request from the fragment. */ 361 if (frag_remaining < desired) { 362 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 363 "There's not enough data in the current fragment " 364 "to serve the request."); 365 /* There's not enough data in the current fragment, 366 * so either just RETURN what we have or fail. */ 367 if (buflen == NULL) { 368 if (frag_remaining > 0) { 369 rd->pending = desired - frag_remaining; 370 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 371 "Remember to collect %u bytes before re-opening", 372 (unsigned) rd->pending); 373 } 374 MBEDTLS_MPS_TRACE_RETURN(MBEDTLS_ERR_MPS_READER_OUT_OF_DATA); 375 } 376 377 desired = frag_remaining; 378 } 379 380 /* There's enough data in the current fragment to serve the 381 * (potentially modified) read request. */ 382 383 frag = rd->frag; 384 frag += frag_fetched; 385 386 *buffer = frag; 387 if (buflen != NULL) { 388 *buflen = desired; 389 } 390 391 end += desired; 392 rd->end = end; 393 rd->pending = 0; 394 MBEDTLS_MPS_TRACE_RETURN(0); 395} 396 397int mbedtls_mps_reader_commit(mbedtls_mps_reader *rd) 398{ 399 mbedtls_mps_size_t end; 400 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_commit"); 401 MBEDTLS_MPS_STATE_VALIDATE_RAW(mps_reader_is_consuming( 402 rd), 403 "mbedtls_mps_reader_commit() requires reader to be in consuming mode"); 404 405 end = rd->end; 406 rd->commit = end; 407 408 MBEDTLS_MPS_TRACE_RETURN(0); 409} 410 411int mbedtls_mps_reader_reclaim(mbedtls_mps_reader *rd, 412 int *paused) 413{ 414 unsigned char *frag, *acc; 415 mbedtls_mps_size_t pending, commit; 416 mbedtls_mps_size_t acc_len, frag_offset, frag_len; 417 MBEDTLS_MPS_TRACE_INIT("mbedtls_mps_reader_reclaim"); 418 419 if (paused != NULL) { 420 *paused = 0; 421 } 422 423 MBEDTLS_MPS_STATE_VALIDATE_RAW(mps_reader_is_consuming( 424 rd), 425 "mbedtls_mps_reader_reclaim() requires reader to be in consuming mode"); 426 427 frag = rd->frag; 428 acc = rd->acc; 429 pending = rd->pending; 430 commit = rd->commit; 431 frag_len = rd->frag_len; 432 433 frag_offset = mps_reader_get_fragment_offset(rd); 434 435 if (pending == 0) { 436 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 437 "No unsatisfied read-request has been logged."); 438 439 /* Check if there's data left to be consumed. */ 440 if (commit < frag_offset || commit - frag_offset < frag_len) { 441 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 442 "There is data left to be consumed."); 443 rd->end = commit; 444 MBEDTLS_MPS_TRACE_RETURN(MBEDTLS_ERR_MPS_READER_DATA_LEFT); 445 } 446 447 rd->acc_available = 0; 448 rd->acc_share.acc_remaining = 0; 449 450 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 451 "Fragment has been fully processed and committed."); 452 } else { 453 int overflow; 454 455 mbedtls_mps_size_t acc_backup_offset; 456 mbedtls_mps_size_t acc_backup_len; 457 mbedtls_mps_size_t frag_backup_offset; 458 mbedtls_mps_size_t frag_backup_len; 459 460 mbedtls_mps_size_t backup_len; 461 mbedtls_mps_size_t acc_len_needed; 462 463 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 464 "There has been an unsatisfied read with %u bytes overhead.", 465 (unsigned) pending); 466 467 if (acc == NULL) { 468 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 469 "No accumulator present"); 470 MBEDTLS_MPS_TRACE_RETURN( 471 MBEDTLS_ERR_MPS_READER_NEED_ACCUMULATOR); 472 } 473 acc_len = rd->acc_len; 474 475 /* Check if the upper layer has already fetched 476 * and committed the contents of the accumulator. */ 477 if (commit < frag_offset) { 478 /* No, accumulator is still being processed. */ 479 frag_backup_offset = 0; 480 frag_backup_len = frag_len; 481 acc_backup_offset = commit; 482 acc_backup_len = frag_offset - commit; 483 } else { 484 /* Yes, the accumulator is already processed. */ 485 frag_backup_offset = commit - frag_offset; 486 frag_backup_len = frag_len - frag_backup_offset; 487 acc_backup_offset = 0; 488 acc_backup_len = 0; 489 } 490 491 backup_len = acc_backup_len + frag_backup_len; 492 acc_len_needed = backup_len + pending; 493 494 overflow = 0; 495 overflow |= (backup_len < acc_backup_len); 496 overflow |= (acc_len_needed < backup_len); 497 498 if (overflow || acc_len < acc_len_needed) { 499 /* Except for the different return code, we behave as if 500 * there hadn't been a call to mbedtls_mps_reader_get() 501 * since the last commit. */ 502 rd->end = commit; 503 rd->pending = 0; 504 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_ERROR, 505 "The accumulator is too small to handle the backup."); 506 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_ERROR, 507 "* Size: %u", (unsigned) acc_len); 508 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_ERROR, 509 "* Needed: %u (%u + %u)", 510 (unsigned) acc_len_needed, 511 (unsigned) backup_len, (unsigned) pending); 512 MBEDTLS_MPS_TRACE_RETURN( 513 MBEDTLS_ERR_MPS_READER_ACCUMULATOR_TOO_SMALL); 514 } 515 516 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 517 "Fragment backup: %u", (unsigned) frag_backup_len); 518 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 519 "Accumulator backup: %u", (unsigned) acc_backup_len); 520 521 /* Move uncommitted parts from the accumulator to the front 522 * of the accumulator. */ 523 memmove(acc, acc + acc_backup_offset, acc_backup_len); 524 525 /* Copy uncommitted parts of the current fragment to the 526 * accumulator. */ 527 memcpy(acc + acc_backup_len, 528 frag + frag_backup_offset, frag_backup_len); 529 530 rd->acc_available = backup_len; 531 rd->acc_share.acc_remaining = pending; 532 533 if (paused != NULL) { 534 *paused = 1; 535 } 536 } 537 538 rd->frag = NULL; 539 rd->frag_len = 0; 540 541 rd->commit = 0; 542 rd->end = 0; 543 rd->pending = 0; 544 545 MBEDTLS_MPS_TRACE(MBEDTLS_MPS_TRACE_TYPE_COMMENT, 546 "Final state: aa %u, al %u, ar %u", 547 (unsigned) rd->acc_available, (unsigned) rd->acc_len, 548 (unsigned) rd->acc_share.acc_remaining); 549 MBEDTLS_MPS_TRACE_RETURN(0); 550} 551 552#endif /* MBEDTLS_SSL_PROTO_TLS1_3 */ 553