| 1 |
/* |
| 2 |
Copyright 2022 The Kubernetes Authors. |
| 3 |
|
| 4 |
Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 |
you may not use this file except in compliance with the License. |
| 6 |
You may obtain a copy of the License at |
| 7 |
|
| 8 |
http://www.apache.org/licenses/LICENSE-2.0 |
| 9 |
|
| 10 |
Unless required by applicable law or agreed to in writing, software |
| 11 |
distributed under the License is distributed on an "AS IS" BASIS, |
| 12 |
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 |
See the License for the specific language governing permissions and |
| 14 |
limitations under the License. |
| 15 |
*/ |
| 16 |
|
| 17 |
package storage |
| 18 |
|
| 19 |
import ( |
| 20 |
"encoding/base64" |
| 21 |
"encoding/json" |
| 22 |
"errors" |
| 23 |
"fmt" |
| 24 |
"path" |
| 25 |
"strings" |
| 26 |
) |
| 27 |
|
| 28 |
var ( |
| 29 |
ErrInvalidStartRV = errors.New("continue key is not valid: incorrect encoded start resourceVersion (version meta.k8s.io/v1)") |
| 30 |
ErrEmptyStartKey = errors.New("continue key is not valid: encoded start key empty (version meta.k8s.io/v1)") |
| 31 |
ErrGenericInvalidKey = errors.New("continue key is not valid") |
| 32 |
ErrUnrecognizedEncodedVersion = errors.New("continue key is not valid: server does not recognize this encoded version") |
| 33 |
) |
| 34 |
|
| 35 |
// continueToken is a simple structured object for encoding the state of a continue token. |
| 36 |
// TODO: if we change the version of the encoded from, we can't start encoding the new version |
| 37 |
// until all other servers are upgraded (i.e. we need to support rolling schema) |
| 38 |
// This is a public API struct and cannot change. |
| 39 |
type continueToken struct { |
| 40 |
APIVersion string `json:"v"` |
| 41 |
ResourceVersion int64 `json:"rv"` |
| 42 |
StartKey string `json:"start"` |
| 43 |
} |
| 44 |
|
| 45 |
// DecodeContinue transforms an encoded predicate from into a versioned struct. |
| 46 |
// TODO: return a typed error that instructs clients that they must relist |
| 47 |
func DecodeContinue(continueValue, keyPrefix string) (fromKey string, rv int64, err error) { |
| 48 |
data, err := base64.RawURLEncoding.DecodeString(continueValue) |
| 49 |
if err != nil { |
| 50 |
return "", 0, fmt.Errorf("%w: %v", ErrGenericInvalidKey, err) |
| 51 |
} |
| 52 |
var c continueToken |
| 53 |
if err := json.Unmarshal(data, &c); err != nil { |
| 54 |
return "", 0, fmt.Errorf("%w: %v", ErrGenericInvalidKey, err) |
| 55 |
} |
| 56 |
switch c.APIVersion { |
| 57 |
case "meta.k8s.io/v1": |
| 58 |
if c.ResourceVersion == 0 { |
| 59 |
return "", 0, ErrInvalidStartRV |
| 60 |
} |
| 61 |
if len(c.StartKey) == 0 { |
| 62 |
return "", 0, ErrEmptyStartKey |
| 63 |
} |
| 64 |
// defend against path traversal attacks by clients - path.Clean will ensure that startKey cannot |
| 65 |
// be at a higher level of the hierarchy, and so when we append the key prefix we will end up with |
| 66 |
// continue start key that is fully qualified and cannot range over anything less specific than |
| 67 |
// keyPrefix. |
| 68 |
key := c.StartKey |
| 69 |
if !strings.HasPrefix(key, "/") { |
| 70 |
key = "/" + key |
| 71 |
} |
| 72 |
cleaned := path.Clean(key) |
| 73 |
if cleaned != key { |
| 74 |
return "", 0, fmt.Errorf("%w: %v", ErrGenericInvalidKey, c.StartKey) |
| 75 |
} |
| 76 |
return keyPrefix + cleaned[1:], c.ResourceVersion, nil |
| 77 |
default: |
| 78 |
return "", 0, fmt.Errorf("%w %v", ErrUnrecognizedEncodedVersion, c.APIVersion) |
| 79 |
} |
| 80 |
} |
| 81 |
|
| 82 |
// EncodeContinue returns a string representing the encoded continuation of the current query. |
| 83 |
func EncodeContinue(key, keyPrefix string, resourceVersion int64) (string, error) { |
| 84 |
nextKey := strings.TrimPrefix(key, keyPrefix) |
| 85 |
if nextKey == key { |
| 86 |
return "", fmt.Errorf("unable to encode next field: the key and key prefix do not match") |
| 87 |
} |
| 88 |
out, err := json.Marshal(&continueToken{APIVersion: "meta.k8s.io/v1", ResourceVersion: resourceVersion, StartKey: nextKey}) |
| 89 |
if err != nil { |
| 90 |
return "", err |
| 91 |
} |
| 92 |
return base64.RawURLEncoding.EncodeToString(out), nil |
| 93 |
} |
| 94 |
|
| 95 |
// PrepareContinueToken prepares optional |
| 96 |
// parameters for retrieving additional results for a paginated request. |
| 97 |
// |
| 98 |
// This function sets up parameters that a client can use to fetch the remaining results |
| 99 |
// from the server if they are available. |
| 100 |
func PrepareContinueToken(keyLastItem, keyPrefix string, resourceVersion int64, itemsCount int64, hasMoreItems bool, opts ListOptions) (string, *int64, error) { |
| 101 |
var remainingItemCount *int64 |
| 102 |
var continueValue string |
| 103 |
var err error |
| 104 |
|
| 105 |
if hasMoreItems { |
| 106 |
// Instruct the client to begin querying from immediately after the last key. |
| 107 |
continueValue, err = EncodeContinue(keyLastItem+"\x00", keyPrefix, resourceVersion) |
| 108 |
if err != nil { |
| 109 |
return "", remainingItemCount, err |
| 110 |
} |
| 111 |
// Etcd response counts in objects that do not match the pred. |
| 112 |
// Instead of returning inaccurate count for non-empty selectors, we return nil. |
| 113 |
// We only set remainingItemCount if the predicate is empty. |
| 114 |
if opts.Predicate.Empty() { |
| 115 |
remainingItems := itemsCount - opts.Predicate.Limit |
| 116 |
remainingItemCount = &remainingItems |
| 117 |
} |
| 118 |
} |
| 119 |
return continueValue, remainingItemCount, err |
| 120 |
} |