https://github.com/torvalds/linux
Revision 4fca50d440cc5d4dc570ad5484cc0b70b381bc2a authored by Jan Kara on 08 September 2022, 09:21:24 UTC, committed by Theodore Ts'o on 22 September 2022, 02:11:34 UTC
One of the side-effects of mb_optimize_scan was that the optimized functions to select next group to try were called even before we tried the goal group. As a result we no longer allocate files close to corresponding inodes as well as we don't try to expand currently allocated extent in the same group. This results in reaim regression with workfile.disk workload of upto 8% with many clients on my test machine: baseline mb_optimize_scan Hmean disk-1 2114.16 ( 0.00%) 2099.37 ( -0.70%) Hmean disk-41 87794.43 ( 0.00%) 83787.47 * -4.56%* Hmean disk-81 148170.73 ( 0.00%) 135527.05 * -8.53%* Hmean disk-121 177506.11 ( 0.00%) 166284.93 * -6.32%* Hmean disk-161 220951.51 ( 0.00%) 207563.39 * -6.06%* Hmean disk-201 208722.74 ( 0.00%) 203235.59 ( -2.63%) Hmean disk-241 222051.60 ( 0.00%) 217705.51 ( -1.96%) Hmean disk-281 252244.17 ( 0.00%) 241132.72 * -4.41%* Hmean disk-321 255844.84 ( 0.00%) 245412.84 * -4.08%* Also this is causing huge regression (time increased by a factor of 5 or so) when untarring archive with lots of small files on some eMMC storage cards. Fix the problem by making sure we try goal group first. Fixes: 196e402adf2e ("ext4: improve cr 0 / cr 1 group scanning") CC: stable@kernel.org Reported-and-tested-by: Stefan Wahren <stefan.wahren@i2se.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Reviewed-by: Ritesh Harjani (IBM) <ritesh.list@gmail.com> Link: https://lore.kernel.org/all/20220727105123.ckwrhbilzrxqpt24@quack3/ Link: https://lore.kernel.org/all/0d81a7c2-46b7-6010-62a4-3e6cfc1628d6@i2se.com/ Signed-off-by: Jan Kara <jack@suse.cz> Link: https://lore.kernel.org/r/20220908092136.11770-1-jack@suse.cz Signed-off-by: Theodore Ts'o <tytso@mit.edu>
1 parent 7e18e42
Tip revision: 4fca50d440cc5d4dc570ad5484cc0b70b381bc2a authored by Jan Kara on 08 September 2022, 09:21:24 UTC
ext4: make mballoc try target group first even with mb_optimize_scan
ext4: make mballoc try target group first even with mb_optimize_scan
Tip revision: 4fca50d
ecrdsa.c
// SPDX-License-Identifier: GPL-2.0+
/*
* Elliptic Curve (Russian) Digital Signature Algorithm for Cryptographic API
*
* Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
*
* References:
* GOST 34.10-2018, GOST R 34.10-2012, RFC 7091, ISO/IEC 14888-3:2018.
*
* Historical references:
* GOST R 34.10-2001, RFC 4357, ISO/IEC 14888-3:2006/Amd 1:2010.
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the Free
* Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*/
#include <linux/module.h>
#include <linux/crypto.h>
#include <crypto/streebog.h>
#include <crypto/internal/akcipher.h>
#include <crypto/internal/ecc.h>
#include <crypto/akcipher.h>
#include <linux/oid_registry.h>
#include <linux/scatterlist.h>
#include "ecrdsa_params.asn1.h"
#include "ecrdsa_pub_key.asn1.h"
#include "ecrdsa_defs.h"
#define ECRDSA_MAX_SIG_SIZE (2 * 512 / 8)
#define ECRDSA_MAX_DIGITS (512 / 64)
struct ecrdsa_ctx {
enum OID algo_oid; /* overall public key oid */
enum OID curve_oid; /* parameter */
enum OID digest_oid; /* parameter */
const struct ecc_curve *curve; /* curve from oid */
unsigned int digest_len; /* parameter (bytes) */
const char *digest; /* digest name from oid */
unsigned int key_len; /* @key length (bytes) */
const char *key; /* raw public key */
struct ecc_point pub_key;
u64 _pubp[2][ECRDSA_MAX_DIGITS]; /* point storage for @pub_key */
};
static const struct ecc_curve *get_curve_by_oid(enum OID oid)
{
switch (oid) {
case OID_gostCPSignA:
case OID_gostTC26Sign256B:
return &gost_cp256a;
case OID_gostCPSignB:
case OID_gostTC26Sign256C:
return &gost_cp256b;
case OID_gostCPSignC:
case OID_gostTC26Sign256D:
return &gost_cp256c;
case OID_gostTC26Sign512A:
return &gost_tc512a;
case OID_gostTC26Sign512B:
return &gost_tc512b;
/* The following two aren't implemented: */
case OID_gostTC26Sign256A:
case OID_gostTC26Sign512C:
default:
return NULL;
}
}
static int ecrdsa_verify(struct akcipher_request *req)
{
struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
unsigned char sig[ECRDSA_MAX_SIG_SIZE];
unsigned char digest[STREEBOG512_DIGEST_SIZE];
unsigned int ndigits = req->dst_len / sizeof(u64);
u64 r[ECRDSA_MAX_DIGITS]; /* witness (r) */
u64 _r[ECRDSA_MAX_DIGITS]; /* -r */
u64 s[ECRDSA_MAX_DIGITS]; /* second part of sig (s) */
u64 e[ECRDSA_MAX_DIGITS]; /* h \mod q */
u64 *v = e; /* e^{-1} \mod q */
u64 z1[ECRDSA_MAX_DIGITS];
u64 *z2 = _r;
struct ecc_point cc = ECC_POINT_INIT(s, e, ndigits); /* reuse s, e */
/*
* Digest value, digest algorithm, and curve (modulus) should have the
* same length (256 or 512 bits), public key and signature should be
* twice bigger.
*/
if (!ctx->curve ||
!ctx->digest ||
!req->src ||
!ctx->pub_key.x ||
req->dst_len != ctx->digest_len ||
req->dst_len != ctx->curve->g.ndigits * sizeof(u64) ||
ctx->pub_key.ndigits != ctx->curve->g.ndigits ||
req->dst_len * 2 != req->src_len ||
WARN_ON(req->src_len > sizeof(sig)) ||
WARN_ON(req->dst_len > sizeof(digest)))
return -EBADMSG;
sg_copy_to_buffer(req->src, sg_nents_for_len(req->src, req->src_len),
sig, req->src_len);
sg_pcopy_to_buffer(req->src,
sg_nents_for_len(req->src,
req->src_len + req->dst_len),
digest, req->dst_len, req->src_len);
vli_from_be64(s, sig, ndigits);
vli_from_be64(r, sig + ndigits * sizeof(u64), ndigits);
/* Step 1: verify that 0 < r < q, 0 < s < q */
if (vli_is_zero(r, ndigits) ||
vli_cmp(r, ctx->curve->n, ndigits) >= 0 ||
vli_is_zero(s, ndigits) ||
vli_cmp(s, ctx->curve->n, ndigits) >= 0)
return -EKEYREJECTED;
/* Step 2: calculate hash (h) of the message (passed as input) */
/* Step 3: calculate e = h \mod q */
vli_from_le64(e, digest, ndigits);
if (vli_cmp(e, ctx->curve->n, ndigits) >= 0)
vli_sub(e, e, ctx->curve->n, ndigits);
if (vli_is_zero(e, ndigits))
e[0] = 1;
/* Step 4: calculate v = e^{-1} \mod q */
vli_mod_inv(v, e, ctx->curve->n, ndigits);
/* Step 5: calculate z_1 = sv \mod q, z_2 = -rv \mod q */
vli_mod_mult_slow(z1, s, v, ctx->curve->n, ndigits);
vli_sub(_r, ctx->curve->n, r, ndigits);
vli_mod_mult_slow(z2, _r, v, ctx->curve->n, ndigits);
/* Step 6: calculate point C = z_1P + z_2Q, and R = x_c \mod q */
ecc_point_mult_shamir(&cc, z1, &ctx->curve->g, z2, &ctx->pub_key,
ctx->curve);
if (vli_cmp(cc.x, ctx->curve->n, ndigits) >= 0)
vli_sub(cc.x, cc.x, ctx->curve->n, ndigits);
/* Step 7: if R == r signature is valid */
if (!vli_cmp(cc.x, r, ndigits))
return 0;
else
return -EKEYREJECTED;
}
int ecrdsa_param_curve(void *context, size_t hdrlen, unsigned char tag,
const void *value, size_t vlen)
{
struct ecrdsa_ctx *ctx = context;
ctx->curve_oid = look_up_OID(value, vlen);
if (!ctx->curve_oid)
return -EINVAL;
ctx->curve = get_curve_by_oid(ctx->curve_oid);
return 0;
}
/* Optional. If present should match expected digest algo OID. */
int ecrdsa_param_digest(void *context, size_t hdrlen, unsigned char tag,
const void *value, size_t vlen)
{
struct ecrdsa_ctx *ctx = context;
int digest_oid = look_up_OID(value, vlen);
if (digest_oid != ctx->digest_oid)
return -EINVAL;
return 0;
}
int ecrdsa_parse_pub_key(void *context, size_t hdrlen, unsigned char tag,
const void *value, size_t vlen)
{
struct ecrdsa_ctx *ctx = context;
ctx->key = value;
ctx->key_len = vlen;
return 0;
}
static u8 *ecrdsa_unpack_u32(u32 *dst, void *src)
{
memcpy(dst, src, sizeof(u32));
return src + sizeof(u32);
}
/* Parse BER encoded subjectPublicKey. */
static int ecrdsa_set_pub_key(struct crypto_akcipher *tfm, const void *key,
unsigned int keylen)
{
struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
unsigned int ndigits;
u32 algo, paramlen;
u8 *params;
int err;
err = asn1_ber_decoder(&ecrdsa_pub_key_decoder, ctx, key, keylen);
if (err < 0)
return err;
/* Key parameters is in the key after keylen. */
params = ecrdsa_unpack_u32(¶mlen,
ecrdsa_unpack_u32(&algo, (u8 *)key + keylen));
if (algo == OID_gost2012PKey256) {
ctx->digest = "streebog256";
ctx->digest_oid = OID_gost2012Digest256;
ctx->digest_len = 256 / 8;
} else if (algo == OID_gost2012PKey512) {
ctx->digest = "streebog512";
ctx->digest_oid = OID_gost2012Digest512;
ctx->digest_len = 512 / 8;
} else
return -ENOPKG;
ctx->algo_oid = algo;
/* Parse SubjectPublicKeyInfo.AlgorithmIdentifier.parameters. */
err = asn1_ber_decoder(&ecrdsa_params_decoder, ctx, params, paramlen);
if (err < 0)
return err;
/*
* Sizes of algo (set in digest_len) and curve should match
* each other.
*/
if (!ctx->curve ||
ctx->curve->g.ndigits * sizeof(u64) != ctx->digest_len)
return -ENOPKG;
/*
* Key is two 256- or 512-bit coordinates which should match
* curve size.
*/
if ((ctx->key_len != (2 * 256 / 8) &&
ctx->key_len != (2 * 512 / 8)) ||
ctx->key_len != ctx->curve->g.ndigits * sizeof(u64) * 2)
return -ENOPKG;
ndigits = ctx->key_len / sizeof(u64) / 2;
ctx->pub_key = ECC_POINT_INIT(ctx->_pubp[0], ctx->_pubp[1], ndigits);
vli_from_le64(ctx->pub_key.x, ctx->key, ndigits);
vli_from_le64(ctx->pub_key.y, ctx->key + ndigits * sizeof(u64),
ndigits);
if (ecc_is_pubkey_valid_partial(ctx->curve, &ctx->pub_key))
return -EKEYREJECTED;
return 0;
}
static unsigned int ecrdsa_max_size(struct crypto_akcipher *tfm)
{
struct ecrdsa_ctx *ctx = akcipher_tfm_ctx(tfm);
/*
* Verify doesn't need any output, so it's just informational
* for keyctl to determine the key bit size.
*/
return ctx->pub_key.ndigits * sizeof(u64);
}
static void ecrdsa_exit_tfm(struct crypto_akcipher *tfm)
{
}
static struct akcipher_alg ecrdsa_alg = {
.verify = ecrdsa_verify,
.set_pub_key = ecrdsa_set_pub_key,
.max_size = ecrdsa_max_size,
.exit = ecrdsa_exit_tfm,
.base = {
.cra_name = "ecrdsa",
.cra_driver_name = "ecrdsa-generic",
.cra_priority = 100,
.cra_module = THIS_MODULE,
.cra_ctxsize = sizeof(struct ecrdsa_ctx),
},
};
static int __init ecrdsa_mod_init(void)
{
return crypto_register_akcipher(&ecrdsa_alg);
}
static void __exit ecrdsa_mod_fini(void)
{
crypto_unregister_akcipher(&ecrdsa_alg);
}
module_init(ecrdsa_mod_init);
module_exit(ecrdsa_mod_fini);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Vitaly Chikunov <vt@altlinux.org>");
MODULE_DESCRIPTION("EC-RDSA generic algorithm");
MODULE_ALIAS_CRYPTO("ecrdsa-generic");
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...