2 * Copyright (c) 2017 Apple Inc. All Rights Reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
21 * @APPLE_LICENSE_HEADER_END@
24 #import "RateLimiter.h"
25 #import <utilities/debugging.h>
26 #import "sec_action.h"
27 #import <CoreFoundation/CFPreferences.h> // For clarity. Also included in debugging.h
29 @interface RateLimiter()
30 @property (readwrite, nonatomic) NSDictionary *config;
31 @property (nonatomic) NSArray<NSMutableDictionary<NSString *, NSDate *> *> *groups;
32 @property (nonatomic) NSDate *lastJudgment;
33 @property (nonatomic) NSDate *overloadUntil;
34 @property (nonatomic) NSString *assetType;
37 @implementation RateLimiter
39 - (instancetype)initWithConfig:(NSDictionary *)config {
49 - (instancetype)initWithCoder:(NSCoder *)coder {
55 _groups = [coder decodeObjectOfClasses:[NSSet setWithObjects: [NSArray class],
56 [NSMutableDictionary class],
61 _overloadUntil = [coder decodeObjectOfClass:[NSDate class] forKey:@"RLoverLoadedUntil"];
62 _lastJudgment = [coder decodeObjectOfClass:[NSDate class] forKey:@"RLlastJudgment"];
63 _assetType = [coder decodeObjectOfClass:[NSString class] forKey:@"RLassetType"];
65 // This list of types might be wrong. Be careful.
66 _config = [coder decodeObjectOfClasses:[NSSet setWithObjects: [NSMutableArray class],
78 - (RateLimiterBadness)judge:(id _Nonnull)obj at:(NSDate * _Nonnull)time limitTime:(NSDate * _Nullable __autoreleasing * _Nonnull)limitTime {
80 //sudo defaults write /Library/Preferences/com.apple.security DisableKeychainRateLimiting -bool YES
81 NSNumber *disabled = CFBridgingRelease(CFPreferencesCopyValue(CFSTR("DisableKeychainRateLimiting"),
82 CFSTR("com.apple.security"),
83 kCFPreferencesAnyUser, kCFPreferencesAnyHost));
84 if ([disabled isKindOfClass:[NSNumber class]] && [disabled boolValue] == YES) {
85 static dispatch_once_t token;
86 static sec_action_t action;
87 dispatch_once(&token, ^{
88 action = sec_action_create("ratelimiterdisabledlogevent", 60);
89 sec_action_set_handler(action, ^{
90 secnotice("ratelimit", "Rate limiting disabled, returning automatic all-clear");
93 sec_action_perform(action);
96 return RateLimiterBadnessClear;
99 RateLimiterBadness badness = RateLimiterBadnessClear;
101 if (self.overloadUntil) {
102 if ([time timeIntervalSinceDate:self.overloadUntil] >= 0) {
105 if (self.overloadUntil) {
106 *limitTime = self.overloadUntil;
107 badness = RateLimiterBadnessOverloaded;
111 if (badness == RateLimiterBadnessClear &&
112 ((self.lastJudgment && [time timeIntervalSinceDate:self.lastJudgment] > [self.config[@"general"][@"maxItemAge"] intValue]) ||
113 [self stateSize] > [self.config[@"general"][@"maxStateSize"] unsignedIntegerValue])) {
115 if (self.overloadUntil) {
116 *limitTime = self.overloadUntil;
117 badness = RateLimiterBadnessOverloaded;
121 if (badness != RateLimiterBadnessClear) {
125 NSDate *resultTime = [NSDate distantPast];
126 for (unsigned long idx = 0; idx < self.groups.count; ++idx) {
127 NSDictionary *groupConfig = self.config[@"groups"][idx];
130 name = groupConfig[@"property"]; // global bucket, does not correspond to object property
132 name = [self getPropertyValue:groupConfig[@"property"] object:obj];
134 // Pretend this property doesn't exist. Should be returning an error instead but currently it's only used with
135 // approved properties 'accessGroup' and 'uuid' and if the item doesn't have either it's sad times anyway.
136 // <rdar://problem/33434425> Improve rate limiter error handling
138 secerror("RateLimiter[%@]: Got nil instead of property named %@", self.config[@"general"][@"name"], groupConfig[@"property"]);
141 NSDate *singleTokenTime = [self consumeTokenFromBucket:self.groups[idx]
145 if (singleTokenTime) {
146 resultTime = [resultTime laterDate:singleTokenTime];
147 badness = MAX([groupConfig[@"badness"] intValue], badness);
151 *limitTime = badness == RateLimiterBadnessClear ? nil : resultTime;
152 self.lastJudgment = time;
156 - (NSDate *)consumeTokenFromBucket:(NSMutableDictionary *)group
157 config:(NSDictionary *)config
158 name:(NSString *)name
160 NSDate *threshold = [time dateByAddingTimeInterval:-([config[@"capacity"] intValue] * [config[@"rate"] intValue])];
161 NSDate *bucket = group[name];
163 if (!bucket || [bucket timeIntervalSinceDate:threshold] < 0) {
167 // Implicitly track the number of tokens in the bucket.
168 // "Would the token I need have been generated in the past or in the future?"
169 bucket = [bucket dateByAddingTimeInterval:[config[@"rate"] intValue]];
170 group[name] = bucket;
171 return ([bucket timeIntervalSinceDate:time] <= 0) ? nil : bucket;
174 - (BOOL)isEqual:(id)object {
175 if (![object isKindOfClass:[RateLimiter class]]) {
178 RateLimiter *other = (RateLimiter *)object;
179 return ([self.config isEqual:other.config] &&
180 [self.groups isEqual:other.groups] &&
181 [self.lastJudgment isEqual:other.lastJudgment] &&
182 ((self.overloadUntil == nil && other.overloadUntil == nil) || [self.overloadUntil isEqual:other.overloadUntil]) &&
183 ((self.assetType == nil && other.assetType == nil) || [self.assetType isEqualToString:other.assetType]));
187 NSMutableArray *newgroups = [NSMutableArray new];
188 for (unsigned long idx = 0; idx < [self.config[@"groups"] count]; ++idx) {
189 [newgroups addObject:[NSMutableDictionary new]];
191 self.groups = newgroups;
192 self.lastJudgment = [NSDate distantPast]; // will cause extraneous trim on first judgment but on empty groups
193 self.overloadUntil = nil;
196 - (void)trim:(NSDate *)time {
197 int threshold = [self.config[@"general"][@"maxItemAge"] intValue];
198 for (NSMutableDictionary *group in self.groups) {
199 NSSet *toRemove = [group keysOfEntriesPassingTest:^BOOL(NSString *key, NSDate *obj, BOOL *stop) {
200 return [time timeIntervalSinceDate:obj] > threshold;
202 [group removeObjectsForKeys:[toRemove allObjects]];
205 if ([self stateSize] > [self.config[@"general"][@"maxStateSize"] unsignedIntegerValue]) {
206 // Trimming did not reduce size (enough), we need to take measures
207 self.overloadUntil = [time dateByAddingTimeInterval:[self.config[@"general"][@"overloadDuration"] unsignedIntValue]];
208 secerror("RateLimiter[%@] state size %lu exceeds max %lu, overloaded until %@",
209 self.config[@"general"][@"name"],
210 (unsigned long)[self stateSize],
211 [self.config[@"general"][@"maxStateSize"] unsignedLongValue],
214 self.overloadUntil = nil;
218 - (NSUInteger)stateSize {
220 for (NSMutableDictionary *group in self.groups) {
221 size += [group count];
226 - (NSString *)diagnostics {
227 return [NSString stringWithFormat:@"RateLimiter[%@]\nconfig:%@\ngroups:%@\noverloaded:%@\nlastJudgment:%@",
228 self.config[@"general"][@"name"],
235 //This could probably be improved, rdar://problem/33416163
236 - (NSString *)getPropertyValue:(NSString *)selectorString object:(id)obj {
237 if ([selectorString isEqualToString:@"accessGroup"] ||
238 [selectorString isEqualToString:@"uuid"]) {
240 SEL selector = NSSelectorFromString(selectorString);
241 IMP imp = [obj methodForSelector:selector];
242 NSString *(*func)(id, SEL) = (void *)imp;
243 return func(obj, selector);
245 seccritical("RateLimter[%@]: \"%@\" is not an approved selector string", self.config[@"general"][@"name"], selectorString);
250 - (void)encodeWithCoder:(NSCoder *)coder {
251 [coder encodeObject:_groups forKey:@"RLgroups"];
252 [coder encodeObject:_overloadUntil forKey:@"RLoverloadedUntil"];
253 [coder encodeObject:_lastJudgment forKey:@"RLlastJudgment"];
254 [coder encodeObject:_assetType forKey:@"RLassetType"];
256 [coder encodeObject:_config forKey:@"RLconfig"];
260 + (BOOL)supportsSecureCoding {