diff options
Diffstat (limited to 'firmware')
-rw-r--r-- | firmware/buflib.c | 137 |
1 files changed, 94 insertions, 43 deletions
diff --git a/firmware/buflib.c b/firmware/buflib.c index 7b1e52eb58..6ffe9335a7 100644 --- a/firmware/buflib.c +++ b/firmware/buflib.c | |||
@@ -97,6 +97,11 @@ | |||
97 | 97 | ||
98 | #define BPANICF panicf | 98 | #define BPANICF panicf |
99 | 99 | ||
100 | /* Available paranoia checks */ | ||
101 | #define PARANOIA_CHECK_LENGTH (1 << 0) | ||
102 | /* Bitmask of enabled paranoia checks */ | ||
103 | #define BUFLIB_PARANOIA 0 | ||
104 | |||
100 | /* Forward indices, used to index a block start pointer as block[fidx_XXX] */ | 105 | /* Forward indices, used to index a block start pointer as block[fidx_XXX] */ |
101 | enum { | 106 | enum { |
102 | fidx_LEN, /* length of the block, must come first */ | 107 | fidx_LEN, /* length of the block, must come first */ |
@@ -129,6 +134,16 @@ static union buflib_data* find_first_free(struct buflib_context *ctx); | |||
129 | static union buflib_data* find_block_before(struct buflib_context *ctx, | 134 | static union buflib_data* find_block_before(struct buflib_context *ctx, |
130 | union buflib_data* block, | 135 | union buflib_data* block, |
131 | bool is_free); | 136 | bool is_free); |
137 | |||
138 | /* Check the length of a block to ensure it does not go beyond the end | ||
139 | * of the allocated area. The block can be either allocated or free. | ||
140 | * | ||
141 | * This verifies that it is safe to iterate to the next block in a loop. | ||
142 | */ | ||
143 | static void check_block_length(struct buflib_context *ctx, | ||
144 | union buflib_data *block); | ||
145 | |||
146 | |||
132 | /* Initialize buffer manager */ | 147 | /* Initialize buffer manager */ |
133 | void | 148 | void |
134 | buflib_init(struct buflib_context *ctx, void *buf, size_t size) | 149 | buflib_init(struct buflib_context *ctx, void *buf, size_t size) |
@@ -380,6 +395,8 @@ buflib_compact(struct buflib_context *ctx) | |||
380 | * For simplicity only 1 hole at a time is considered */ | 395 | * For simplicity only 1 hole at a time is considered */ |
381 | for(block = find_first_free(ctx); block < ctx->alloc_end; block += len) | 396 | for(block = find_first_free(ctx); block < ctx->alloc_end; block += len) |
382 | { | 397 | { |
398 | check_block_length(ctx, block); | ||
399 | |||
383 | bool movable = true; /* cache result to avoid 2nd call to move_block */ | 400 | bool movable = true; /* cache result to avoid 2nd call to move_block */ |
384 | len = block->val; | 401 | len = block->val; |
385 | /* This block is free, add its length to the shift value */ | 402 | /* This block is free, add its length to the shift value */ |
@@ -456,7 +473,8 @@ buflib_compact_and_shrink(struct buflib_context *ctx, unsigned shrink_hints) | |||
456 | this < ctx->alloc_end; | 473 | this < ctx->alloc_end; |
457 | before = this, this += abs(this->val)) | 474 | before = this, this += abs(this->val)) |
458 | { | 475 | { |
459 | if (this->val <= 0) | 476 | check_block_length(ctx, this); |
477 | if (this->val < 0) | ||
460 | continue; | 478 | continue; |
461 | 479 | ||
462 | struct buflib_callbacks *ops = this[fidx_OPS].ops; | 480 | struct buflib_callbacks *ops = this[fidx_OPS].ops; |
@@ -622,7 +640,7 @@ buffer_alloc: | |||
622 | /* need to re-evaluate last before the loop because the last allocation | 640 | /* need to re-evaluate last before the loop because the last allocation |
623 | * possibly made room in its front to fit this, so last would be wrong */ | 641 | * possibly made room in its front to fit this, so last would be wrong */ |
624 | last = false; | 642 | last = false; |
625 | for (block = find_first_free(ctx);;block += block_len) | 643 | for (block = find_first_free(ctx);; block += block_len) |
626 | { | 644 | { |
627 | /* If the last used block extends all the way to the handle table, the | 645 | /* If the last used block extends all the way to the handle table, the |
628 | * block "after" it doesn't have a header. Because of this, it's easier | 646 | * block "after" it doesn't have a header. Because of this, it's easier |
@@ -638,6 +656,8 @@ buffer_alloc: | |||
638 | block = NULL; | 656 | block = NULL; |
639 | break; | 657 | break; |
640 | } | 658 | } |
659 | |||
660 | check_block_length(ctx, block); | ||
641 | block_len = block->val; | 661 | block_len = block->val; |
642 | /* blocks with positive length are already allocated. */ | 662 | /* blocks with positive length are already allocated. */ |
643 | if(block_len > 0) | 663 | if(block_len > 0) |
@@ -697,13 +717,14 @@ buffer_alloc: | |||
697 | static union buflib_data* | 717 | static union buflib_data* |
698 | find_first_free(struct buflib_context *ctx) | 718 | find_first_free(struct buflib_context *ctx) |
699 | { | 719 | { |
700 | union buflib_data* ret = ctx->buf_start; | 720 | union buflib_data *ret; |
701 | while(ret < ctx->alloc_end) | 721 | for(ret = ctx->buf_start; ret < ctx->alloc_end; ret += ret->val) |
702 | { | 722 | { |
723 | check_block_length(ctx, ret); | ||
703 | if (ret->val < 0) | 724 | if (ret->val < 0) |
704 | break; | 725 | break; |
705 | ret += ret->val; | ||
706 | } | 726 | } |
727 | |||
707 | /* ret is now either a free block or the same as alloc_end, both is fine */ | 728 | /* ret is now either a free block or the same as alloc_end, both is fine */ |
708 | return ret; | 729 | return ret; |
709 | } | 730 | } |
@@ -723,6 +744,7 @@ find_block_before(struct buflib_context *ctx, union buflib_data* block, | |||
723 | /* find the block that's before the current one */ | 744 | /* find the block that's before the current one */ |
724 | while (next_block != block) | 745 | while (next_block != block) |
725 | { | 746 | { |
747 | check_block_length(ctx, ret); | ||
726 | ret = next_block; | 748 | ret = next_block; |
727 | next_block += abs(ret->val); | 749 | next_block += abs(ret->val); |
728 | } | 750 | } |
@@ -796,24 +818,31 @@ free_space_at_end(struct buflib_context* ctx) | |||
796 | size_t | 818 | size_t |
797 | buflib_allocatable(struct buflib_context* ctx) | 819 | buflib_allocatable(struct buflib_context* ctx) |
798 | { | 820 | { |
799 | union buflib_data *this; | ||
800 | size_t free_space = 0, max_free_space = 0; | 821 | size_t free_space = 0, max_free_space = 0; |
822 | intptr_t block_len; | ||
801 | 823 | ||
802 | /* make sure buffer is as contiguous as possible */ | 824 | /* make sure buffer is as contiguous as possible */ |
803 | if (!ctx->compact) | 825 | if (!ctx->compact) |
804 | buflib_compact(ctx); | 826 | buflib_compact(ctx); |
805 | 827 | ||
806 | /* now look if there's free in holes */ | 828 | /* now look if there's free in holes */ |
807 | for(this = find_first_free(ctx); this < ctx->alloc_end; this += abs(this->val)) | 829 | for(union buflib_data *block = find_first_free(ctx); |
830 | block < ctx->alloc_end; | ||
831 | block += block_len) | ||
808 | { | 832 | { |
809 | if (this->val < 0) | 833 | check_block_length(ctx, block); |
834 | block_len = block->val; | ||
835 | |||
836 | if (block_len < 0) | ||
810 | { | 837 | { |
811 | free_space += -this->val; | 838 | block_len = -block_len; |
839 | free_space += block_len; | ||
812 | continue; | 840 | continue; |
813 | } | 841 | } |
842 | |||
814 | /* an unmovable section resets the count as free space | 843 | /* an unmovable section resets the count as free space |
815 | * can't be contigous */ | 844 | * can't be contigous */ |
816 | if (!IS_MOVABLE(this)) | 845 | if (!IS_MOVABLE(block)) |
817 | { | 846 | { |
818 | if (max_free_space < free_space) | 847 | if (max_free_space < free_space) |
819 | max_free_space = free_space; | 848 | max_free_space = free_space; |
@@ -836,17 +865,16 @@ buflib_allocatable(struct buflib_context* ctx) | |||
836 | size_t | 865 | size_t |
837 | buflib_available(struct buflib_context* ctx) | 866 | buflib_available(struct buflib_context* ctx) |
838 | { | 867 | { |
839 | union buflib_data *this; | ||
840 | size_t free_space = 0; | 868 | size_t free_space = 0; |
841 | 869 | ||
842 | /* now look if there's free in holes */ | 870 | /* add up all holes */ |
843 | for(this = find_first_free(ctx); this < ctx->alloc_end; this += abs(this->val)) | 871 | for(union buflib_data *block = find_first_free(ctx); |
872 | block < ctx->alloc_end; | ||
873 | block += abs(block->val)) | ||
844 | { | 874 | { |
845 | if (this->val < 0) | 875 | check_block_length(ctx, block); |
846 | { | 876 | if (block->val < 0) |
847 | free_space += -this->val; | 877 | free_space += -block->val; |
848 | continue; | ||
849 | } | ||
850 | } | 878 | } |
851 | 879 | ||
852 | free_space *= sizeof(union buflib_data); /* make it bytes */ | 880 | free_space *= sizeof(union buflib_data); /* make it bytes */ |
@@ -988,16 +1016,17 @@ void *buflib_get_data(struct buflib_context *ctx, int handle) | |||
988 | 1016 | ||
989 | void buflib_check_valid(struct buflib_context *ctx) | 1017 | void buflib_check_valid(struct buflib_context *ctx) |
990 | { | 1018 | { |
991 | for(union buflib_data* this = ctx->buf_start; | 1019 | for(union buflib_data *block = ctx->buf_start; |
992 | this < ctx->alloc_end; | 1020 | block < ctx->alloc_end; |
993 | this += abs(this->val)) | 1021 | block += abs(block->val)) |
994 | { | 1022 | { |
995 | if (this->val < 0) | 1023 | check_block_length(ctx, block); |
1024 | if (block->val < 0) | ||
996 | continue; | 1025 | continue; |
997 | 1026 | ||
998 | union buflib_data *h_entry = this[fidx_HANDLE].handle; | 1027 | union buflib_data *h_entry = block[fidx_HANDLE].handle; |
999 | union buflib_data *block_end = userpointer_to_block_end(h_entry->alloc); | 1028 | union buflib_data *block_end = userpointer_to_block_end(h_entry->alloc); |
1000 | uint32_t crc = calc_block_crc(this, block_end); | 1029 | uint32_t crc = calc_block_crc(block, block_end); |
1001 | if (crc != block_end[-bidx_CRC].crc) | 1030 | if (crc != block_end[-bidx_CRC].crc) |
1002 | { | 1031 | { |
1003 | buflib_panic(ctx, "crc mismatch: 0x%08x, expected: 0x%08x", | 1032 | buflib_panic(ctx, "crc mismatch: 0x%08x, expected: 0x%08x", |
@@ -1038,13 +1067,16 @@ void buflib_print_blocks(struct buflib_context *ctx, | |||
1038 | { | 1067 | { |
1039 | char buf[128]; | 1068 | char buf[128]; |
1040 | int i = 0; | 1069 | int i = 0; |
1041 | for(union buflib_data* this = ctx->buf_start; | 1070 | |
1042 | this < ctx->alloc_end; | 1071 | for(union buflib_data *block = ctx->buf_start; |
1043 | this += abs(this->val)) | 1072 | block != ctx->alloc_end; |
1073 | block += abs(block->val)) | ||
1044 | { | 1074 | { |
1075 | check_block_length(ctx, block); | ||
1076 | |||
1045 | snprintf(buf, sizeof(buf), "%8p: val: %4ld (%s)", | 1077 | snprintf(buf, sizeof(buf), "%8p: val: %4ld (%s)", |
1046 | this, this->val, | 1078 | block, (long)block->val, |
1047 | this->val > 0 ? this[fidx_NAME].name : "<unallocated>"); | 1079 | block->val > 0 ? block[fidx_NAME].name : "<unallocated>"); |
1048 | print(i++, buf); | 1080 | print(i++, buf); |
1049 | } | 1081 | } |
1050 | } | 1082 | } |
@@ -1054,28 +1086,47 @@ void buflib_print_blocks(struct buflib_context *ctx, | |||
1054 | int buflib_get_num_blocks(struct buflib_context *ctx) | 1086 | int buflib_get_num_blocks(struct buflib_context *ctx) |
1055 | { | 1087 | { |
1056 | int i = 0; | 1088 | int i = 0; |
1057 | for(union buflib_data* this = ctx->buf_start; | 1089 | for(union buflib_data *block = ctx->buf_start; |
1058 | this < ctx->alloc_end; | 1090 | block < ctx->alloc_end; |
1059 | this += abs(this->val)) | 1091 | block += abs(block->val)) |
1060 | { | 1092 | { |
1061 | i++; | 1093 | check_block_length(ctx, block); |
1094 | ++i; | ||
1062 | } | 1095 | } |
1063 | return i; | 1096 | return i; |
1064 | } | 1097 | } |
1065 | 1098 | ||
1066 | void buflib_print_block_at(struct buflib_context *ctx, int block_num, | 1099 | void buflib_print_block_at(struct buflib_context *ctx, int block_num, |
1067 | char* buf, size_t bufsize) | 1100 | char* buf, size_t bufsize) |
1068 | { | 1101 | { |
1069 | union buflib_data* this = ctx->buf_start; | 1102 | for(union buflib_data *block = ctx->buf_start; |
1070 | while(block_num > 0 && this < ctx->alloc_end) | 1103 | block < ctx->alloc_end; |
1104 | block += abs(block->val)) | ||
1071 | { | 1105 | { |
1072 | this += abs(this->val); | 1106 | check_block_length(ctx, block); |
1073 | block_num -= 1; | ||
1074 | } | ||
1075 | 1107 | ||
1076 | snprintf(buf, bufsize, "%8p: val: %4ld (%s)", | 1108 | if (block_num-- == 0) |
1077 | this, (long)this->val, | 1109 | { |
1078 | this->val > 0 ? this[fidx_NAME].name : "<unallocated>"); | 1110 | snprintf(buf, bufsize, "%8p: val: %4ld (%s)", |
1111 | block, (long)block->val, | ||
1112 | block->val > 0 ? block[fidx_NAME].name : "<unallocated>"); | ||
1113 | } | ||
1114 | } | ||
1079 | } | 1115 | } |
1080 | |||
1081 | #endif | 1116 | #endif |
1117 | |||
1118 | static void check_block_length(struct buflib_context *ctx, | ||
1119 | union buflib_data *block) | ||
1120 | { | ||
1121 | if (BUFLIB_PARANOIA & PARANOIA_CHECK_LENGTH) | ||
1122 | { | ||
1123 | intptr_t length = block[fidx_LEN].val; | ||
1124 | |||
1125 | /* Check the block length does not pass beyond the end */ | ||
1126 | if (length == 0 || block > ctx->alloc_end - abs(length)) | ||
1127 | { | ||
1128 | buflib_panic(ctx, "block len wacky [%p]=%ld", | ||
1129 | (void*)&block[fidx_LEN], (long)length); | ||
1130 | } | ||
1131 | } | ||
1132 | } | ||