canonicalize-test.c++ (14488B)
1 // Copyright (c) 2016 Sandstorm Development Group, Inc. and contributors 2 // Licensed under the MIT License: 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a copy 5 // of this software and associated documentation files (the "Software"), to deal 6 // in the Software without restriction, including without limitation the rights 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 // copies of the Software, and to permit persons to whom the Software is 9 // furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 // THE SOFTWARE. 21 22 #include "message.h" 23 #include "any.h" 24 #include <kj/debug.h> 25 #include <kj/test.h> 26 #include "test-util.h" 27 28 namespace capnp { 29 namespace _ { // private 30 using test::TestLists; 31 namespace { 32 33 34 KJ_TEST("canonicalize yields canonical message") { 35 MallocMessageBuilder builder; 36 auto root = builder.initRoot<TestAllTypes>(); 37 38 initTestMessage(root); 39 40 auto canonicalWords = canonicalize(root.asReader()); 41 // Throws an exception on canonicalization failure. 42 43 kj::ArrayPtr<const capnp::word> canonicalSegments[1] = {canonicalWords.asPtr()}; 44 capnp::SegmentArrayMessageReader canonicalReader(kj::arrayPtr(canonicalSegments, 1)); 45 46 KJ_ASSERT(AnyStruct::Reader(root.asReader()) == 47 AnyStruct::Reader(canonicalReader.getRoot<TestAllTypes>())); 48 } 49 50 KJ_TEST("canonicalize succeeds on empty struct") { 51 MallocMessageBuilder builder; 52 auto root = builder.initRoot<TestAllTypes>(); 53 54 canonicalize(root.asReader()); // Throws an exception on canoncalization failure. 55 } 56 57 KJ_TEST("data word with only its most significant bit set does not get truncated") { 58 AlignedData<3> segment = {{ 59 // Struct pointer, body immediately follows, two data words 60 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 61 62 // First data word 63 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 64 65 // Second data word, all zero except most significant bit 66 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 67 }}; 68 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 3)}; 69 SegmentArrayMessageReader messageReader(kj::arrayPtr(segments, 1)); 70 71 KJ_ASSERT(messageReader.isCanonical()); 72 auto canonicalWords = canonicalize(messageReader.getRoot<TestAllTypes>()); 73 74 // At one point this failed because an off-by-one bug in canonicalization 75 // caused the second word of the data section to be truncated. 76 ASSERT_EQ(canonicalWords.asBytes(), kj::arrayPtr(segment.bytes, 3 * 8)); 77 } 78 79 KJ_TEST("INLINE_COMPOSITE data word with only its most significant bit set does not get truncated") { 80 AlignedData<5> segment = {{ 81 // Struct pointer, body immediately follows, one pointer 82 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 83 84 // List pointer, no offset, inline composite, two words long 85 0x01, 0x00, 0x00, 0x00, 0x17, 0x00, 0x00, 0x00, 86 87 // Tag word, list has one element with two data words and no pointers 88 0x04, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 89 90 // First data word 91 0x22, 0x22, 0x22, 0x22, 0x22, 0x22, 0x22, 0x22, 92 93 // Second data word, all zero except most significant bit 94 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 95 }}; 96 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 5)}; 97 SegmentArrayMessageReader messageReader(kj::arrayPtr(segments, 1)); 98 99 KJ_ASSERT(messageReader.isCanonical()); 100 auto canonicalWords = canonicalize(messageReader.getRoot<TestLists>()); 101 102 // At one point this failed because an off-by-one bug in canonicalization 103 // caused the second word of the data section to be truncated. 104 ASSERT_EQ(canonicalWords.asBytes(), kj::arrayPtr(segment.bytes, 5 * 8)); 105 } 106 107 KJ_TEST("canonical non-null empty struct field") { 108 AlignedData<4> nonNullEmptyStruct = {{ 109 // Struct pointer, body immediately follows, two pointer fields, no data. 110 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 111 112 // First pointer field, struct, offset of 1, data size 1, no pointers. 113 0x04, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 114 115 // Non-null pointer to empty struct. 116 0xfc, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 117 118 // Body of struct filled with non-zero data. 119 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 120 }}; 121 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(nonNullEmptyStruct.words, 4)}; 122 SegmentArrayMessageReader messageReader(kj::arrayPtr(segments, 1)); 123 124 KJ_ASSERT(messageReader.isCanonical()); 125 } 126 127 KJ_TEST("for pointers to empty structs, preorder is not canonical") { 128 AlignedData<4> nonNullEmptyStruct = {{ 129 // Struct pointer, body immediately follows, two pointer fields, no data. 130 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 131 132 // First pointer field, struct, offset of 1, data size 1, no pointers. 133 0x04, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 134 135 // Non-null pointer to empty struct. Offset puts it in "preorder". Would need to have 136 // an offset of -1 to be canonical. 137 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 138 139 // Body of struct filled with non-zero data. 140 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 0xee, 141 }}; 142 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(nonNullEmptyStruct.words, 4)}; 143 SegmentArrayMessageReader messageReader(kj::arrayPtr(segments, 1)); 144 145 KJ_ASSERT(!messageReader.isCanonical()); 146 } 147 148 KJ_TEST("isCanonical requires pointer preorder") { 149 AlignedData<5> misorderedSegment = {{ 150 //Struct pointer, data immediately follows, two pointer fields, no data 151 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 152 //Pointer field 1, pointing to the last entry, data size 1, no pointer 153 0x08, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 154 //Pointer field 2, pointing to the next entry, data size 2, no pointer 155 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 156 //Data for field 2 157 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 158 //Data for field 1 159 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 160 }}; 161 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(misorderedSegment.words, 162 5)}; 163 SegmentArrayMessageReader outOfOrder(kj::arrayPtr(segments, 1)); 164 165 KJ_ASSERT(!outOfOrder.isCanonical()); 166 } 167 168 KJ_TEST("isCanonical requires dense packing") { 169 AlignedData<3> gapSegment = {{ 170 //Struct pointer, data after a gap 171 0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 172 //The gap 173 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 174 //Data for field 1 175 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 176 }}; 177 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(gapSegment.words, 178 3)}; 179 SegmentArrayMessageReader gap(kj::arrayPtr(segments, 1)); 180 181 KJ_ASSERT(!gap.isCanonical()); 182 } 183 184 KJ_TEST("isCanonical rejects multi-segment messages") { 185 AlignedData<1> farPtr = {{ 186 //Far pointer to next segment 187 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 188 }}; 189 190 AlignedData<2> farTarget = {{ 191 //Struct pointer (needed to make the far pointer legal) 192 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 193 //Dummy data 194 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 195 }}; 196 197 kj::ArrayPtr<const word> segments[2] = { 198 kj::arrayPtr(farPtr.words, 1), 199 kj::arrayPtr(farTarget.words, 2) 200 }; 201 202 SegmentArrayMessageReader multiSegmentMessage(kj::arrayPtr(segments, 2)); 203 KJ_ASSERT(!multiSegmentMessage.isCanonical()); 204 } 205 206 KJ_TEST("isCanonical rejects zero segment messages") { 207 SegmentArrayMessageReader zero(kj::arrayPtr((kj::ArrayPtr<const word>*)NULL, 208 0)); 209 KJ_ASSERT(!zero.isCanonical()); 210 } 211 212 KJ_TEST("isCanonical requires truncation of 0-valued struct fields") { 213 AlignedData<2> nonTruncatedSegment = {{ 214 //Struct pointer, data immediately follows 215 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 216 //Default data value, should have been truncated 217 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 218 }}; 219 kj::ArrayPtr<const word> segments[1] = { 220 kj::arrayPtr(nonTruncatedSegment.words, 3) 221 }; 222 SegmentArrayMessageReader nonTruncated(kj::arrayPtr(segments, 1)); 223 224 KJ_ASSERT(!nonTruncated.isCanonical()); 225 } 226 227 KJ_TEST("isCanonical rejects unused trailing words") { 228 AlignedData<3> segment = {{ 229 // Struct pointer, data in next word 230 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 231 232 // Data section of struct 233 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 234 235 // Trailing zero word 236 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 237 }}; 238 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 3)}; 239 SegmentArrayMessageReader message(kj::arrayPtr(segments, 1)); 240 241 KJ_ASSERT(!message.isCanonical()); 242 } 243 244 KJ_TEST("isCanonical accepts empty inline composite list of zero-sized structs") { 245 AlignedData<3> segment = {{ 246 // Struct pointer, pointer in next word 247 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 248 249 // List pointer, inline composite, zero words long 250 0x01, 0x00, 0x00, 0x00, 0x07, 0x00, 0x00, 0x00, 251 252 // Tag word 253 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 254 }}; 255 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 3)}; 256 SegmentArrayMessageReader message(kj::arrayPtr(segments, 1)); 257 258 KJ_ASSERT(message.isCanonical()); 259 } 260 261 KJ_TEST("isCanonical rejects inline composite list with inaccurate word-length") { 262 AlignedData<6> segment = {{ 263 // Struct pointer, no offset, pointer section has two entries 264 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 265 266 // List pointer, offset of one, inline composite, two words long 267 // (The list only needs to be one word long to hold its actual elements; 268 // therefore this message is not canonical.) 269 0x05, 0x00, 0x00, 0x00, 0x17, 0x00, 0x00, 0x00, 270 271 // Struct pointer, offset two, data section has one word 272 0x08, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 273 274 // Tag word, struct, one element, one word data section 275 0x04, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 276 277 // Data section of struct element of list 278 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 279 280 // Data section of struct field in top-level struct 281 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 282 }}; 283 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 6)}; 284 SegmentArrayMessageReader message(kj::arrayPtr(segments, 1)); 285 286 KJ_ASSERT(!message.isCanonical()); 287 } 288 289 KJ_TEST("upgraded lists can be canonicalized") { 290 AlignedData<7> upgradedList = {{ 291 //Struct pointer, data immediately follows, 4 pointer fields, no data 292 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, 293 //Three words of default pointers to get to the int16 list 294 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 295 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 296 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 297 //List pointer, 3 int16s. 298 0x01, 0x00, 0x00, 0x00, 0x33, 0x00, 0x00, 0x00, 299 //First two elements 300 0x00, 0x01, 0x02, 0x03, 0x04, 0x04, 0x05, 0x06, 301 //Last element 302 0x07, 0x08, 0x09, 0x10, 0x00, 0x00, 0x00, 0x00 303 }}; 304 kj::ArrayPtr<const word> segments[1] = { 305 kj::arrayPtr(upgradedList.words, 7) 306 }; 307 SegmentArrayMessageReader upgraded(kj::arrayPtr(segments, 1)); 308 309 auto root = upgraded.getRoot<TestLists>(); 310 canonicalize(root); 311 } 312 313 KJ_TEST("isCanonical requires truncation of 0-valued struct fields in all list members") { 314 AlignedData<6> nonTruncatedList = {{ 315 //List pointer, composite, 316 0x01, 0x00, 0x00, 0x00, 0x27, 0x00, 0x00, 0x00, 317 //Struct tag word, 2 structs, 2 data words per struct 318 0x08, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 319 //Data word non-null 320 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 321 //Null trailing word 322 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 323 //Data word non-null 324 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 325 //Null trailing word 326 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 327 }}; 328 kj::ArrayPtr<const word> segments[1] = { 329 kj::arrayPtr(nonTruncatedList.words, 6) 330 }; 331 SegmentArrayMessageReader nonTruncated(kj::arrayPtr(segments, 1)); 332 333 KJ_ASSERT(!nonTruncated.isCanonical()); 334 } 335 336 KJ_TEST("primitive list with nonzero padding") { 337 AlignedData<3> segment = {{ 338 // Struct, one pointer field. 339 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 340 341 // List of three byte-sized elements. 342 0x01, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 343 344 // Fourth byte is non-zero! 345 0x01, 0x02, 0x03, 0x01, 0x00, 0x00, 0x00, 0x00, 346 }}; 347 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 3)}; 348 SegmentArrayMessageReader message(kj::arrayPtr(segments, 1)); 349 350 KJ_ASSERT(!message.isCanonical()); 351 352 auto canonicalWords = canonicalize(message.getRoot<test::TestAnyPointer>()); 353 354 AlignedData<3> canonicalSegment = {{ 355 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 356 0x01, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 357 0x01, 0x02, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 358 }}; 359 360 ASSERT_EQ(canonicalWords.asBytes(), kj::arrayPtr(canonicalSegment.bytes, 3 * 8)); 361 } 362 363 KJ_TEST("bit list with nonzero padding") { 364 AlignedData<3> segment = {{ 365 // Struct, one pointer field. 366 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 367 368 // List of eleven bit-sized elements. 369 0x01, 0x00, 0x00, 0x00, 0x59, 0x00, 0x00, 0x00, 370 371 // Twelfth bit is non-zero! 372 0xee, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 373 }}; 374 kj::ArrayPtr<const word> segments[1] = {kj::arrayPtr(segment.words, 3)}; 375 SegmentArrayMessageReader message(kj::arrayPtr(segments, 1)); 376 377 KJ_ASSERT(!message.isCanonical()); 378 379 auto canonicalWords = canonicalize(message.getRoot<test::TestAnyPointer>()); 380 381 AlignedData<3> canonicalSegment = {{ 382 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 383 0x01, 0x00, 0x00, 0x00, 0x59, 0x00, 0x00, 0x00, 384 0xee, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 385 }}; 386 387 ASSERT_EQ(canonicalWords.asBytes(), kj::arrayPtr(canonicalSegment.bytes, 3 * 8)); 388 } 389 390 } // namespace 391 } // namespace _ (private) 392 } // namespace capnp