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
,