2 * Copyright (C) 2015 Michael Brown <mbrown@fensystems.co.uk>.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
28 #include <ipxe/uaccess.h>
29 #include <ipxe/sha256.h>
30 #include <ipxe/sha512.h>
31 #include <ipxe/hmac.h>
32 #include <ipxe/base16.h>
33 #include <ipxe/pccrc.h>
37 * Peer Content Caching and Retrieval: Content Identification [MS-PCCRC]
41 /******************************************************************************
45 ******************************************************************************
49 * Transcribe hash value (for debugging)
51 * @v info Content information
53 * @ret string Hash value string
55 static inline const char *
56 peerdist_info_hash_ntoa ( const struct peerdist_info *info, const void *hash ) {
57 static char buf[ ( 2 * PEERDIST_DIGEST_MAX_SIZE ) + 1 /* NUL */ ];
58 size_t digestsize = info->digestsize;
61 assert ( info != NULL );
62 assert ( digestsize != 0 );
63 assert ( base16_encoded_len ( digestsize ) < sizeof ( buf ) );
65 /* Transcribe hash value */
66 base16_encode ( hash, digestsize, buf, sizeof ( buf ) );
73 * @v info Content information
75 * @v offset Starting offset
77 * @ret rc Return status code
79 static int peerdist_info_get ( const struct peerdist_info *info, void *data,
80 size_t offset, size_t len ) {
83 if ( ( offset > info->raw.len ) ||
84 ( len > ( info->raw.len - offset ) ) ) {
85 DBGC ( info, "PCCRC %p data underrun at [%zx,%zx) of %zx\n",
86 info, offset, ( offset + len ), info->raw.len );
91 copy_from_user ( data, info->raw.data, offset, len );
97 * Populate segment hashes
99 * @v segment Content information segment to fill in
100 * @v hash Segment hash of data
101 * @v secret Segment secret
103 static void peerdist_info_segment_hash ( struct peerdist_info_segment *segment,
104 const void *hash, const void *secret ){
105 const struct peerdist_info *info = segment->info;
106 struct digest_algorithm *digest = info->digest;
107 uint8_t ctx[digest->ctxsize];
108 size_t digestsize = info->digestsize;
109 size_t secretsize = digestsize;
110 static const uint16_t magic[] = PEERDIST_SEGMENT_ID_MAGIC;
113 assert ( digestsize <= sizeof ( segment->hash ) );
114 assert ( digestsize <= sizeof ( segment->secret ) );
115 assert ( digestsize <= sizeof ( segment->id ) );
117 /* Get segment hash of data */
118 memcpy ( segment->hash, hash, digestsize );
120 /* Get segment secret */
121 memcpy ( segment->secret, secret, digestsize );
123 /* Calculate segment identifier */
124 hmac_init ( digest, ctx, segment->secret, &secretsize );
125 assert ( secretsize == digestsize );
126 hmac_update ( digest, ctx, segment->hash, digestsize );
127 hmac_update ( digest, ctx, magic, sizeof ( magic ) );
128 hmac_final ( digest, ctx, segment->secret, &secretsize, segment->id );
129 assert ( secretsize == digestsize );
132 /******************************************************************************
134 * Content Information version 1
136 ******************************************************************************
140 * Get number of blocks within a block description
142 * @v info Content information
143 * @v offset Block description offset
144 * @ret blocks Number of blocks, or negative error
146 static int peerdist_info_v1_blocks ( const struct peerdist_info *info,
148 struct peerdist_info_v1_block raw;
152 /* Get block description header */
153 if ( ( rc = peerdist_info_get ( info, &raw, offset,
154 sizeof ( raw ) ) ) != 0 )
157 /* Calculate number of blocks */
158 blocks = le32_to_cpu ( raw.blocks );
164 * Locate block description
166 * @v info Content information
167 * @v index Segment index
168 * @ret offset Block description offset, or negative error
170 static ssize_t peerdist_info_v1_block_offset ( const struct peerdist_info *info,
171 unsigned int index ) {
172 size_t digestsize = info->digestsize;
179 assert ( index < info->segments );
181 /* Calculate offset of first block description */
182 offset = ( sizeof ( struct peerdist_info_v1 ) +
184 sizeof ( peerdist_info_v1_segment_t ( digestsize ) ) ) );
186 /* Iterate over block descriptions until we find this segment */
187 for ( i = 0 ; i < index ; i++ ) {
189 /* Get number of blocks */
190 blocks = peerdist_info_v1_blocks ( info, offset );
193 DBGC ( info, "PCCRC %p segment %d could not get number "
194 "of blocks: %s\n", info, i, strerror ( rc ) );
198 /* Move to next block description */
199 offset += sizeof ( peerdist_info_v1_block_t ( digestsize,
207 * Populate content information
209 * @v info Content information to fill in
210 * @ret rc Return status code
212 static int peerdist_info_v1 ( struct peerdist_info *info ) {
213 struct peerdist_info_v1 raw;
214 struct peerdist_info_segment first;
215 struct peerdist_info_segment last;
222 if ( ( rc = peerdist_info_get ( info, &raw, 0, sizeof ( raw ) ) ) != 0){
223 DBGC ( info, "PCCRC %p could not get V1 content information: "
224 "%s\n", info, strerror ( rc ) );
227 assert ( raw.version.raw == cpu_to_le16 ( PEERDIST_INFO_V1 ) );
229 /* Determine hash algorithm */
230 switch ( raw.hash ) {
231 case cpu_to_le32 ( PEERDIST_INFO_V1_HASH_SHA256 ) :
232 info->digest = &sha256_algorithm;
234 case cpu_to_le32 ( PEERDIST_INFO_V1_HASH_SHA384 ) :
235 info->digest = &sha384_algorithm;
237 case cpu_to_le32 ( PEERDIST_INFO_V1_HASH_SHA512 ) :
238 info->digest = &sha512_algorithm;
241 DBGC ( info, "PCCRC %p unsupported hash algorithm %#08x\n",
242 info, le32_to_cpu ( raw.hash ) );
245 info->digestsize = info->digest->digestsize;
246 assert ( info->digest != NULL );
247 DBGC2 ( info, "PCCRC %p using %s[%zd]\n",
248 info, info->digest->name, ( info->digestsize * 8 ) );
250 /* Calculate number of segments */
251 info->segments = le32_to_cpu ( raw.segments );
253 /* Get first segment */
254 if ( ( rc = peerdist_info_segment ( info, &first, 0 ) ) != 0 )
257 /* Calculate range start offset */
258 info->range.start = first.range.start;
260 /* Calculate trimmed range start offset */
261 first_skip = le32_to_cpu ( raw.first );
262 info->trim.start = ( first.range.start + first_skip );
264 /* Get last segment */
265 if ( ( rc = peerdist_info_segment ( info, &last,
266 ( info->segments - 1 ) ) ) != 0 )
269 /* Calculate range end offset */
270 info->range.end = last.range.end;
272 /* Calculate trimmed range end offset */
274 /* Explicit length to include from last segment is given */
275 last_read = le32_to_cpu ( raw.last );
276 last_skip = ( last.index ? 0 : first_skip );
277 info->trim.end = ( last.range.start + last_skip + last_read );
279 /* No explicit length given: range extends to end of segment */
280 info->trim.end = last.range.end;
287 * Populate content information segment
289 * @v segment Content information segment to fill in
290 * @ret rc Return status code
292 static int peerdist_info_v1_segment ( struct peerdist_info_segment *segment ) {
293 const struct peerdist_info *info = segment->info;
294 size_t digestsize = info->digestsize;
295 peerdist_info_v1_segment_t ( digestsize ) raw;
301 assert ( segment->index < info->segments );
303 /* Get raw description */
304 raw_offset = ( sizeof ( struct peerdist_info_v1 ) +
305 ( segment->index * sizeof ( raw ) ) );
306 if ( ( rc = peerdist_info_get ( info, &raw, raw_offset,
307 sizeof ( raw ) ) ) != 0 ) {
308 DBGC ( info, "PCCRC %p segment %d could not get segment "
309 "description: %s\n", info, segment->index,
314 /* Calculate start offset of this segment */
315 segment->range.start = le64_to_cpu ( raw.segment.offset );
317 /* Calculate end offset of this segment */
318 segment->range.end = ( segment->range.start +
319 le32_to_cpu ( raw.segment.len ) );
321 /* Calculate block size of this segment */
322 segment->blksize = le32_to_cpu ( raw.segment.blksize );
324 /* Locate block description for this segment */
325 raw_offset = peerdist_info_v1_block_offset ( info, segment->index );
326 if ( raw_offset < 0 ) {
331 /* Get number of blocks */
332 blocks = peerdist_info_v1_blocks ( info, raw_offset );
335 DBGC ( info, "PCCRC %p segment %d could not get number of "
336 "blocks: %s\n", info, segment->index, strerror ( rc ) );
339 segment->blocks = blocks;
341 /* Calculate segment hashes */
342 peerdist_info_segment_hash ( segment, raw.hash, raw.secret );
348 * Populate content information block
350 * @v block Content information block to fill in
351 * @ret rc Return status code
353 static int peerdist_info_v1_block ( struct peerdist_info_block *block ) {
354 const struct peerdist_info_segment *segment = block->segment;
355 const struct peerdist_info *info = segment->info;
356 size_t digestsize = info->digestsize;
357 peerdist_info_v1_block_t ( digestsize, segment->blocks ) raw;
362 assert ( block->index < segment->blocks );
364 /* Calculate start offset of this block */
365 block->range.start = ( segment->range.start +
366 ( block->index * segment->blksize ) );
368 /* Calculate end offset of this block */
369 block->range.end = ( block->range.start + segment->blksize );
370 if ( block->range.end > segment->range.end )
371 block->range.end = segment->range.end;
373 /* Locate block description */
374 raw_offset = peerdist_info_v1_block_offset ( info, segment->index );
375 if ( raw_offset < 0 ) {
381 raw_offset += offsetof ( typeof ( raw ), hash[block->index] );
382 if ( ( rc = peerdist_info_get ( info, block->hash, raw_offset,
383 digestsize ) ) != 0 ) {
384 DBGC ( info, "PCCRC %p segment %d block %d could not get "
385 "hash: %s\n", info, segment->index, block->index,
393 /** Content information version 1 operations */
394 static struct peerdist_info_operations peerdist_info_v1_operations = {
395 .info = peerdist_info_v1,
396 .segment = peerdist_info_v1_segment,
397 .block = peerdist_info_v1_block,
400 /******************************************************************************
402 * Content Information version 2
404 ******************************************************************************
407 /** A segment cursor */
408 struct peerdist_info_v2_cursor {
409 /** Raw data offset */
411 /** Number of segments remaining within this chunk */
412 unsigned int remaining;
413 /** Accumulated segment length */
418 * Initialise segment cursor
420 * @v cursor Segment cursor
423 peerdist_info_v2_cursor_init ( struct peerdist_info_v2_cursor *cursor ) {
425 /* Initialise cursor */
426 cursor->offset = ( sizeof ( struct peerdist_info_v2 ) +
427 sizeof ( struct peerdist_info_v2_chunk ) );
428 cursor->remaining = 0;
433 * Update segment cursor to next segment description
435 * @v info Content information
436 * @v offset Current offset
437 * @v remaining Number of segments remaining within this chunk
438 * @ret rc Return status code
441 peerdist_info_v2_cursor_next ( const struct peerdist_info *info,
442 struct peerdist_info_v2_cursor *cursor ) {
443 size_t digestsize = info->digestsize;
444 peerdist_info_v2_segment_t ( digestsize ) raw;
445 struct peerdist_info_v2_chunk chunk;
448 /* Get chunk description if applicable */
449 if ( ! cursor->remaining ) {
451 /* Get chunk description */
452 if ( ( rc = peerdist_info_get ( info, &chunk,
455 sizeof ( chunk ) ) ) != 0 )
458 /* Update number of segments remaining */
459 cursor->remaining = ( be32_to_cpu ( chunk.len ) /
463 /* Get segment description header */
464 if ( ( rc = peerdist_info_get ( info, &raw.segment, cursor->offset,
465 sizeof ( raw.segment ) ) ) != 0 )
469 cursor->offset += sizeof ( raw );
471 if ( ! cursor->remaining )
472 cursor->offset += sizeof ( chunk );
473 cursor->len += be32_to_cpu ( raw.segment.len );
479 * Get number of segments and total length
481 * @v info Content information
482 * @v len Length to fill in
483 * @ret rc Number of segments, or negative error
485 static int peerdist_info_v2_segments ( const struct peerdist_info *info,
487 struct peerdist_info_v2_cursor cursor;
488 unsigned int segments;
491 /* Iterate over all segments */
492 for ( peerdist_info_v2_cursor_init ( &cursor ), segments = 0 ;
493 cursor.offset < info->raw.len ; segments++ ) {
495 /* Update segment cursor */
496 if ( ( rc = peerdist_info_v2_cursor_next ( info,
498 DBGC ( info, "PCCRC %p segment %d could not update "
499 "segment cursor: %s\n",
500 info, segments, strerror ( rc ) );
505 /* Record accumulated length */
512 * Populate content information
514 * @v info Content information to fill in
515 * @ret rc Return status code
517 static int peerdist_info_v2 ( struct peerdist_info *info ) {
518 struct peerdist_info_v2 raw;
524 if ( ( rc = peerdist_info_get ( info, &raw, 0, sizeof ( raw ) ) ) != 0){
525 DBGC ( info, "PCCRC %p could not get V2 content information: "
526 "%s\n", info, strerror ( rc ) );
529 assert ( raw.version.raw == cpu_to_le16 ( PEERDIST_INFO_V2 ) );
531 /* Determine hash algorithm */
532 switch ( raw.hash ) {
533 case PEERDIST_INFO_V2_HASH_SHA512_TRUNC :
534 info->digest = &sha512_algorithm;
535 info->digestsize = ( 256 / 8 );
538 DBGC ( info, "PCCRC %p unsupported hash algorithm %#02x\n",
542 assert ( info->digest != NULL );
543 DBGC2 ( info, "PCCRC %p using %s[%zd]\n",
544 info, info->digest->name, ( info->digestsize * 8 ) );
546 /* Calculate number of segments and total length */
547 segments = peerdist_info_v2_segments ( info, &len );
548 if ( segments < 0 ) {
550 DBGC ( info, "PCCRC %p could not get segment count and length: "
551 "%s\n", info, strerror ( rc ) );
554 info->segments = segments;
556 /* Calculate range start offset */
557 info->range.start = be64_to_cpu ( raw.offset );
559 /* Calculate trimmed range start offset */
560 info->trim.start = ( info->range.start + be32_to_cpu ( raw.first ) );
562 /* Calculate range end offset */
563 info->range.end = ( info->range.start + len );
565 /* Calculate trimmed range end offset */
566 info->trim.end = ( raw.len ? be64_to_cpu ( raw.len ) :
573 * Populate content information segment
575 * @v segment Content information segment to fill in
576 * @ret rc Return status code
578 static int peerdist_info_v2_segment ( struct peerdist_info_segment *segment ) {
579 const struct peerdist_info *info = segment->info;
580 size_t digestsize = info->digestsize;
581 peerdist_info_v2_segment_t ( digestsize ) raw;
582 struct peerdist_info_v2_cursor cursor;
588 assert ( segment->index < info->segments );
590 /* Iterate over all segments before the target segment */
591 for ( peerdist_info_v2_cursor_init ( &cursor ), index = 0 ;
592 index < segment->index ; index++ ) {
594 /* Update segment cursor */
595 if ( ( rc = peerdist_info_v2_cursor_next ( info,
597 DBGC ( info, "PCCRC %p segment %d could not update "
598 "segment cursor: %s\n",
599 info, index, strerror ( rc ) );
604 /* Get raw description */
605 if ( ( rc = peerdist_info_get ( info, &raw, cursor.offset,
606 sizeof ( raw ) ) ) != 0 ) {
607 DBGC ( info, "PCCRC %p segment %d could not get segment "
609 info, segment->index, strerror ( rc ) );
613 /* Calculate start offset of this segment */
614 segment->range.start = ( info->range.start + cursor.len );
616 /* Calculate end offset of this segment */
617 len = be32_to_cpu ( raw.segment.len );
618 segment->range.end = ( segment->range.start + len );
620 /* Model as a segment containing a single block */
622 segment->blksize = len;
624 /* Calculate segment hashes */
625 peerdist_info_segment_hash ( segment, raw.hash, raw.secret );
631 * Populate content information block
633 * @v block Content information block to fill in
634 * @ret rc Return status code
636 static int peerdist_info_v2_block ( struct peerdist_info_block *block ) {
637 const struct peerdist_info_segment *segment = block->segment;
638 const struct peerdist_info *info = segment->info;
639 size_t digestsize = info->digestsize;
642 assert ( block->index < segment->blocks );
644 /* Model as a block covering the whole segment */
645 memcpy ( &block->range, &segment->range, sizeof ( block->range ) );
646 memcpy ( block->hash, segment->hash, digestsize );
651 /** Content information version 2 operations */
652 static struct peerdist_info_operations peerdist_info_v2_operations = {
653 .block = peerdist_info_v2_block,
654 .segment = peerdist_info_v2_segment,
655 .info = peerdist_info_v2,
658 /******************************************************************************
660 * Content Information
662 ******************************************************************************
666 * Populate content information
669 * @v len Length of raw data
670 * @v info Content information to fill in
671 * @ret rc Return status code
673 int peerdist_info ( userptr_t data, size_t len, struct peerdist_info *info ) {
674 union peerdist_info_version version;
677 /* Initialise structure */
678 memset ( info, 0, sizeof ( *info ) );
679 info->raw.data = data;
683 if ( ( rc = peerdist_info_get ( info, &version, 0,
684 sizeof ( version ) ) ) != 0 ) {
685 DBGC ( info, "PCCRC %p could not get version: %s\n",
686 info, strerror ( rc ) );
689 DBGC2 ( info, "PCCRC %p version %d.%d\n",
690 info, version.major, version.minor );
692 /* Determine version */
693 switch ( version.raw ) {
694 case cpu_to_le16 ( PEERDIST_INFO_V1 ) :
695 info->op = &peerdist_info_v1_operations;
697 case cpu_to_le16 ( PEERDIST_INFO_V2 ) :
698 info->op = &peerdist_info_v2_operations;
701 DBGC ( info, "PCCRC %p unsupported version %d.%d\n",
702 info, version.major, version.minor );
705 assert ( info->op != NULL );
706 assert ( info->op->info != NULL );
708 /* Populate content information */
709 if ( ( rc = info->op->info ( info ) ) != 0 )
712 DBGC2 ( info, "PCCRC %p range [%08zx,%08zx) covers [%08zx,%08zx) with "
713 "%d segments\n", info, info->range.start, info->range.end,
714 info->trim.start, info->trim.end, info->segments );
719 * Populate content information segment
721 * @v info Content information
722 * @v segment Content information segment to fill in
723 * @v index Segment index
724 * @ret rc Return status code
726 int peerdist_info_segment ( const struct peerdist_info *info,
727 struct peerdist_info_segment *segment,
728 unsigned int index ) {
732 assert ( info != NULL );
733 assert ( info->op != NULL );
734 assert ( info->op->segment != NULL );
735 if ( index >= info->segments ) {
736 DBGC ( info, "PCCRC %p segment %d of [0,%d) out of range\n",
737 info, index, info->segments );
741 /* Initialise structure */
742 memset ( segment, 0, sizeof ( *segment ) );
743 segment->info = info;
744 segment->index = index;
746 /* Populate content information segment */
747 if ( ( rc = info->op->segment ( segment ) ) != 0 )
750 DBGC2 ( info, "PCCRC %p segment %d range [%08zx,%08zx) with %d "
751 "blocks\n", info, segment->index, segment->range.start,
752 segment->range.end, segment->blocks );
753 DBGC2 ( info, "PCCRC %p segment %d digest %s\n", info, segment->index,
754 peerdist_info_hash_ntoa ( info, segment->hash ) );
755 DBGC2 ( info, "PCCRC %p segment %d secret %s\n", info, segment->index,
756 peerdist_info_hash_ntoa ( info, segment->secret ) );
757 DBGC2 ( info, "PCCRC %p segment %d identf %s\n", info, segment->index,
758 peerdist_info_hash_ntoa ( info, segment->id ) );
763 * Populate content information block
765 * @v segment Content information segment
766 * @v block Content information block to fill in
767 * @v index Block index
768 * @ret rc Return status code
770 int peerdist_info_block ( const struct peerdist_info_segment *segment,
771 struct peerdist_info_block *block,
772 unsigned int index ) {
773 const struct peerdist_info *info = segment->info;
779 assert ( segment != NULL );
780 assert ( info != NULL );
781 assert ( info->op != NULL );
782 assert ( info->op->block != NULL );
783 if ( index >= segment->blocks ) {
784 DBGC ( info, "PCCRC %p segment %d block %d of [0,%d) out of "
785 "range\n", info, segment->index, index, segment->blocks);
789 /* Initialise structure */
790 memset ( block, 0, sizeof ( *block ) );
791 block->segment = segment;
792 block->index = index;
794 /* Populate content information block */
795 if ( ( rc = info->op->block ( block ) ) != 0 )
798 /* Calculate trimmed range */
799 start = block->range.start;
800 if ( start < info->trim.start )
801 start = info->trim.start;
802 end = block->range.end;
803 if ( end > info->trim.end )
804 end = info->trim.end;
807 block->trim.start = start;
808 block->trim.end = end;
810 DBGC2 ( info, "PCCRC %p segment %d block %d hash %s\n",
811 info, segment->index, block->index,
812 peerdist_info_hash_ntoa ( info, block->hash ) );
813 DBGC2 ( info, "PCCRC %p segment %d block %d range [%08zx,%08zx) covers "
814 "[%08zx,%08zx)\n", info, segment->index, block->index,
815 block->range.start, block->range.end, block->trim.start,